Iterating Transducers

Issue title: Special issue in memoriam of Yurii Rogozhin

Article type: Research Article

Authors: Sutner, K.

Affiliations: Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA. sutner@cs.cmu.edu

Note: [] Address for correspondence: Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213

Abstract: We discuss simple functional transductions defined by invertible Mealy automata under iteration and in particular the question when the orbit relation defined by iteration is rational. We identify a class of these automata that has relatively complicated orbits, yet some of them are still orbit rational and discuss a number of decision problems associated with these devices.

DOI: 10.3233/FI-2015-1211

Journal: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 259-272, 2015