1 Streaming String Transducers
1.1 Two-way Streaming String Transducers
We define the notion of two way streaming string transducer as a streaming string transducer with registers, where the head can move in both directions. Let \(f\) be a function from \(\Sigma^*\) to \(\Gamma^*\). Prove that the following are equivalent:
- \(f\) is computed by a streaming string transducer.
- \(f\) is computed by a two-way streaming string transducer.
2 Commutativity
This section is inspired by the Ph.D. thesis of Douéneau-Tabot (2023), and particularly of its Chapter 5 called Polyregular functions with commutative outputs on page 123.
A function \(f\) is commutative when, for all \(n \in \mathbb{N}\), for all permutation \(\sigma \in \mathcal{S}_n\), for all \(w \in \Sigma^n\), \(f(w) = f(\sigma(w))\). A function has unary output when the output alphabet is \(\{ 1 \}\).
2.1 Deciding Commutativity
Let \(f\) be a function from \(\Sigma^*\) to \(\Gamma^*\) computed by a 2DFT. Is it decidable whether \(f\) is commutative?
2.2 Unary Output
Let \(f\) be a function from \(\Sigma^*\) to \(\{ 1 \}^*\). Prove that the following are equivalent:
- \(f\) is computed by a 2DFT.
- \(f\) is computed by a rational function.
This is Theorem 5.15 in the case \(k = 1\) in Douéneau-Tabot (2023).
2.3 Rational Series
A rational series is a function from \(\Sigma^*\) to \(K\) where \(K\) is a semi-ring that is computed by a weighted automaton. We recall that a weighted automaton \(W\) is a finite (non-deterministic) automaton with weights in \(\mathbb{R}\), whose semantics is defined as \(W(w)\) is the sum over all accepting runs of \(W\) of the product of the weights along this path. Equivalently, a weighted automaton is defined in terms of monoids by a morphism \(\mu \colon \Sigma^* \to \mathcal{M}_{n,n}(\mathbb{R})\) and a linear map \(\lambda \colon \mathcal{M}_{n,n}(\mathbb{R}) \to \mathbb{R}\), such that \(W(w) :=\lambda(\mu(w))\).
We define counting formulas as a generalisation of the correspondence between \(\mathbb{MSO}\) and regular languages to the case of rational series. A counting formula is a formula \(\varphi \in \mathbb{MSO}\) with first-order and second-order free variables, whose semantics is given by \(\# \varphi(w) := \left| \left\{\nu \text{ valuation } \mid w, \nu \models \varphi(w)\right\} \right|\).
Prove that the following are equivalent:
- \(f\) is computed by a weighted automaton with \(\mathbb{N}\)-output,
- \(f\) is computed by a counting formula.
What happens if you restrict formulas to be in \(\mathbb{FO}\)?