Abstract
We study iterated transductions, where the basic transductions are given by a class of length-preserving invertible transducers over the binary alphabet. It is shown that in some cases the resulting orbit relation is rational and we determine the complexity of several natural computational problems associated with the iterated transductions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bartholdi, L., Silva, P.V.: Groups defined by automata. In: CoRR, abs/1012.1531 (2010)
Berstel, J.: Transductions and context-free languages (2009), http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions.html
Cook, M.: Universality in elementary cellular automata. Complex Systems 15(1), 1–40 (2004)
Fortnow, L., Grochow, J.A.: Complexity classes of equivalence problems revisited. Inf. Comput. 209(4), 748–763 (2011)
Gluškov, V.M.: Abstract theory of automata. Uspehi Mat. Nauk. 16(5(101)), 3–62 (1961)
Grigorchuk, R., Šunić, Z.: Self-Similarity and Branching in Group Theory. In: Groups St. Andrews 2005. London Math. Soc. Lec. Notes, vol. 339. Cambridge University Press (2007)
Grigorchuk, R.R., Nekrashevich, V.V., Sushchanski, V.I.: Automata, dynamical systems and groups. Proc. Steklov Institute of Math. 231, 128–203 (2000)
Howard Johnson, J.: Rational equivalence relations. Theoretical Computer Science 47, 167–176 (1986)
Khoussainov, B., Nerode, A.: Automatic presentations of structures. In: Leivant, D. (ed.) LCC 1994. LNCS, vol. 960, pp. 367–392. Springer, Heidelberg (1995)
Khoussainov, B., Nerode, A.: Automata Theory and its Applications. Birkhäuser (2001)
Khoussainov, B., Rubin, S.: Automatic structures: overview and future directions. J. Autom. Lang. Comb. 8(2), 287–301 (2003)
Knuth, D.: Private communication (2010)
Latteux, M., Simplot, D., Terlutte, A.: Iterated length-preserving rational transductions. In: Brim, L., Gruska, J., Zlatuška, J. (eds.) MFCS 1998. LNCS, vol. 1450, pp. 286–295. Springer, Heidelberg (1998)
Neary, T., Woods, D.: P-completeness of cellular automaton rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 132–143. Springer, Heidelberg (2006)
Nekrashevych, V.: Self-Similar Groups. AMS. Math. Surveys and Monographs, vol. 117 (2005)
Nekrashevych, V., Sidki, S.: Automorphisms of the binary tree: state-closed subgroups and dynamics of 1/2-endomorphisms. Cambridge University Press (2004)
Raney, G.N.: Sequential functions. J. Assoc. Comp. Mach. 5(2), 177–180 (1958)
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press (2009)
Serre, J.-P.: Arbres, Amalgames, SL 2. Astérisque Société Mathématique de France, Paris (1977)
Sidki, S.: Automorphisms of one-rooted trees: Growth, circuit structure, and acyclicity. J. Math. Sciences 100(1), 1925–1943 (2000)
Sutner, K.: On the computational complexity of finite cellular automata. J. Comput. System Sci. 50(1), 87–97 (1995)
Sutner, K.: Universality and cellular automata. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol. 3354, pp. 50–59. Springer, Heidelberg (2005)
Sutner, K.: Computational classification of cellular automata. Int. J. General Systems 41(6), 1–13 (2012)
Sutner, K.: Invertible transducers, iteration and coordinates. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol. 7982, pp. 306–318. Springer, Heidelberg (2013)
Sutner, K., Lewi, K.: Iterating invertible binary transducers. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 294–306. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sutner, K. (2013). Invertible Transductions and Iteration. In: Jurgensen, H., Reis, R. (eds) Descriptional Complexity of Formal Systems. DCFS 2013. Lecture Notes in Computer Science, vol 8031. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39310-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-39310-5_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39309-9
Online ISBN: 978-3-642-39310-5
eBook Packages: Computer ScienceComputer Science (R0)