PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Iterating Transducers

Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
259--272
Opis fizyczny
Bibliogr. 38 poz., rys.
Twórcy
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-0b416b05-bbdf-4117-9bab-2bcea9020f81
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.