Iterating transducers (Q2805459)

This article discusses certain properties of the iteration of functions computed by certain simple invertable transducers. The transducers are the usual deterministic finite-state transducers or Mealy automata. Since the questions discussed are undecidable even for small transducers in the general case, the author restricts himself to invertable transducers in which for each current state \(q\) the outgoing transitions of \(q\) implement a permutation on the input and output symbols. Given a function \(f : \Sigma^* \to \Sigma^*\), the function \(f^n : \Sigma^* \to \Sigma^*\) is the \(n\)-fold (functional) composition of \(f\) with \(f^0\) being the identity. The iteration of \(f\) is the relation \(f^* = \bigcup_{n \geq 0} f^n\); i.e., it encodes the reachability relation of two given strings \(x\) and \(y\) in a chain of applications of \(f\). Note that whereas all \(f^n\) are functions, the iteration \(f^*\) is only a relation.NEWLINENEWLINEThe main question discussed is whether for a given rational function \(f\) the induced iteration \(f^*\) is also rational. As a first result the author reproves that this question is undecidable for length-preserving transducers. Even invertable transducers can still compute (transformation) groups that are very difficult, so a further restriction requires the transducer to be ``cycle-cum-chord'', which makes sure that the computed groups are reasonably simple. Indeed, the transduction semigroup of those transducers is even abelian. Using Knuth normal form, the authors demonstrate that the equality \(f^* = g^*\) is decidable in polynomial time for functions computed by certain limited cycle-cum-chord transducers. However, not all cycle-cum-chord transducers afford a rational iteration, which is demonstrated by a positive and a negative example. Finally, two additional problems, the timestamp problem and the coordinate problem, are discussed. Given a rational function \(f\) and strings \(x\) and \(y\), the timestamp problem asks for the least integer \(n\) such that \(f^n(x) = y\), if such an integer exists. An efficient (quadratic-time) algorithm for the timestamp problem for cycle-cum-chord transducers is also supplied.NEWLINENEWLINEThe paper is well written but refers heavily to algebra and uses its terms. A solid background in linear and abstract algebra is certainly required to understand the paper. All related notions are mentioned and all related research is properly credited. Often, several viewpoints are offered, which helps readers with different backgrounds. The references given in the paper also help to understand it, and it is often beneficial to consult the cited literature for the original constructions. Nevertheless, the ideas of the constructions can easily be understood without additional literature.