Iterating Transducers

• Autorzy: Sutner K.

Identyfikatory

DOI

10.3233/FI-2015-1211

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

finite state machine; decision making; problem solving; iterative methods; computational complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 259--272
• Opis fizyczny: Bibliogr. 38 poz., rys.

Twórcy

autor

Sutner K.

• Computer Science Department, Carnegie Mellon University Pittsburgh, PA 15213, USA

Bibliografia

• [1] J. Berstel. Transductions and context-free languages. http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions.html, 2009.
• [2] J. A. Brzozowski. Derivatives of regular expressions. Journal Assoc. for Comp. Machinery, 11, 1964.
• [3] M. Cook. Universality in elementary cellular automata. Complex Systems, 15(1):1–40, 2004.
• [4] D. Dams, Y. Lakhnech, and M. Steffen. Iterating transducers. J. Log. Algebr. Program., 52-53:109–127, 2002.
• [5] M. Davis. A note on universal Turing machines, volume 34 of Annals of Mathematics Studies, pages 167–175. Princeton University Press, 1956.
• [6] M. Davis. The definition of universal Turingmachines. Proc. of the AmericanMathematical Society, 8:1125–1126, 1957.
• [7] S. Eilenberg. Automata, Languages and Machines, volume A. Academic Press, 1974.
• [8] C. C. Elgot and J. E. Mezei. On relations defined by generalized finite automata. IBM J. Res. Dev., 9:47–68, January 1965.
• [9] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Patterson, and W. P. Thurston. Word Processing in Groups. Jones and Bartlett, Burlington, 1992.
• [10] P. Gillibert. The finiteness problem for automaton semigroups is undecidable. ArXiv e-prints, 2013.
• [11] V. M. Gluˇskov. Abstract theory of automata. Uspehi Mat. Nauk, 16(5(101)):3–62, 1961.
• [12] R. R. Grigorchuk, V. V. Nekrashevich, and V. I. Sushchanski. Automata, dynamical systems and groups. Proc. Steklov Institute of Math., 231:128–203, 2000.
• [13] L. Harrington and S. Shelah. The undecidability of the recursively enumerable degrees. Bull. Amer. Math. Soc., 6:79–80, 1982.
• [14] B. Khoussainov and A. Nerode. Automatic presentations of structures. In LCC ’94: Int.Workshop on Logical and Computational Complexity, pages 367–392, London, UK, 1995. Springer-Verlag.
• [15] B. Khoussainov and S. Rubin. Automatic structures: overview and future directions. J. Autom. Lang. Comb., 8(2):287–301, 2003.
• [16] I. Klimann and M. Picantin. A characterization of those automata that structurally generate finite groups. ArXiv e-prints, 2013.
• [17] D. Knuth. Private communication, 2010.
• [18] M. Latteux, D. Simplot, and A. Terlutte. Iterated length-preserving rational transductions. In Proc. 23rd Symposium on Mathematical Foundations of Computer Science, pages 286–295. Springer-Verlag, 1998.
• [19] T. Neary and D. Woods. P-completeness of cellular automaton rule 110. In ICALP, volume 4051 of LNCS, pages 132–143. Springer, 2006.
• [20] V. Nekrashevych. Self-Similar Groups, volume 117 of Math. Surveys and Monographs. AMS, 2005.
• [21] V. Nekrashevych and S. Sidki. Automorphisms of the binary tree: state-closed subgroups and dynamics of 1/2-endomorphisms. Cambridge University Press, 2004.
• [22] G. N. Raney. Sequential functions. J. Assoc. Comp. Mach., 5(2):177–180, 1958.
• [23] Y. Rogozhin. Small universal turing machines. Theor. Comput. Sci., 168(2):215–240, 1996.
• [24] J. Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009.
• [25] D. Scott. Some definitional suggestions for automata theory. J. Comput. Syst. Sci., 1(2):187–212, August 1967.
• [26] J.-P. Serre. Arbres, Amalgames, SL2. Number 46 in Ast´erisque. Soci´et´e Math´ematique de France, Paris, 1977.
• [27] S. Sidki. Automorphisms of one-rooted trees: Growth, circuit structure, and acyclicity. J. Math. Sciences, 100(1):1925–1943, 2000.
• [28] K. Sutner. A note on Culik-Yu classes. Complex Systems, 3(1):107–115, 1989.
• [29] K. Sutner. Classifying circular cellular automata. Phys. D, 45(1–3):386–395, 1990.
• [30] K. Sutner. Cellular automata and intermediate reachability problems. Fundamenta Informaticae, 52(1-3):249–256, 2002.
• [31] K. Sutner. The complexity of reversible cellular automata. Theoretical Computer Science, 325(2):317–328, 2004.
• [32] K. Sutner. Model checking one-dimensional cellular automata. J. Cellular Automata, 4(3):213–224, 2009.
• [33] K. Sutner. Computational classification of cellular automata. Int. J. General Systems, 41(6):1–13, 2012.
• [34] K. Sutner. Invertible transducers and iteration. In H. Juergensen and R. Reis, editors, Descriptional Complexity of Formal Systems, volume 8031 of Lecture Notes in Computer Science, pages 18–29. Springer Berlin, 2013.
• [35] K. Sutner. Iteration of invertible transductions. IJFCS, 2014.
• [36] K. Sutner and K. Lewi. Iterating invertible binary transducers. In M. Kutrib, N. Moreira, and R. Reis, editors, Descriptional Complexity of Formal Systems, volume 7386 of Lecture Notes in Computer Science, pages 294–306. Springer Berlin, 2012.
• [37] J. Vuillemin. On circuits and numbers. IEEE Transactions on Computers, 43:868–879, 1994.
• [38] S. Wolfram. A New Kind of Science. Wolfram Media, Champaign, IL, 2002.