Infinite Traces and Symbolic Dynamics - the Minimal Shift Case

• Autorzy: Foryś, W. , Oprocha, P.
• Języki publikacji: EN

Abstrakty

EN

We study interrelations between symbolic descriptions of concurrently evolving systems and underlying sequential dynamics. The basic framework for this research is formulated on the background of the theory of traces. We focus our interests on minimal shifts and t-shifts generated by them, that is shifts defined in the space of infinite real traces. We show that sets of infinite real traces generated by minimal shifts are always closed and, under some conditions, are also tshifts. Additional discussion for the case of small alphabets (containing at most four letters) is also provided.

Słowa kluczowe

EN

word; trace; shifts; shift on traces; minimal shift

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 2
• Strony: 147-161
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Foryś, W.

autor

Oprocha, P.

• Institute of Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Krak´ow, Poland,

Bibliografia

• [1] J. Auslander, Minimal flows and their extensions, North-Holland Mathematics Studies, 153. North-Holland Publishing Co., Amsterdam, 1988
• [2] J. Berstel and D. Perrin, Theory of codes, Pure and Applied Mathematics, vol. 117, Academic Press Inc., Orlando, FL, 1985.
• [3] O. Bournez andM. Cosnard, On the computational power of dynamical systems and hybrid systems, Theoret. Comput. Sci. 168 (1996), 417-459.
• [4] P. Cartier and D. Foata. Problèmes combinatories de commutation et réarrangements. Lecture Notes in Mathematics. Springer-Verlag, 1969.
• [5] V. Diekert. Combinatorics on Traces. Lectures Notes in Computer Science. Springer Verlag, Berlin, 1990.
• [6] V. Diekert and Y. M´etivier. Partial commutation and traces. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 8, pages 457-534. Springer-Verlag, 1997.
• [7] V. Diekert and G. Rozenberg, editors. The book of traces. World Scientific Publishing Co. Inc., River Edge, NJ, 1995.
• [8] T. Downarowicz, Survey of odometers and Toeplitz flows. Algebraic and topological dynamics, 7-37, Contemp. Math., 385, Amer. Math. Soc., Providence, RI, 2005.
• [9] P. Kurka, On topological dynamics of Turing machines, Theoret. Comput. Sci. 174 (1997), 203-216.
• [10] M. Kwiatkowska, A metric for traces, Inform. Process. Lett., 35 (1990), 129-135.
• [11] W. Foryś and P. Oprocha, Infinite Traces and Symbolic Dynamics, Theory Comput Syst., 45 (2009), 133-149.
• [12] D. Lind and B. Marcus. Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995.
• [13] A.Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. Aarhus University, 78 (1977) 1-45.
• [14] M. Morse and G. A. Hedlund, Symbolic Dynamics, Am. J. Math., 60 (1938) 815-866.
• [15] , Symbolic dynamics. II. Sturmian trajectories, Am. J. Math., 62 (1940) 1-42 .
• [16] C. Moore, Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett. 64 (1990), 2354-2357.
• [17] P. Oprocha, On entropy and Turing machine with moving tape dynamical model, Nonlinearity, 19 (2006) 2475-2487.
• [18] M. Queffelec, Substitution Dynamical Systems - Spectral Analysis Springer-Verlag, LNM, 1294 1987.
• [19] A. Restivo, Finitely generated sofic systems, Theoret. Comput. Sci., 65 (1989), 265-270.
• [20] H. T. Siegelmann, Neural networks and analog computation, Progress in Theoretical Computer Science, Birkh¨auser Boston Inc., Boston, MA, 1999, Beyond the Turing limit.
• [21] H. T. Siegelmann and S. Fishman, Analog computation with dynamical systems, Physica D 120 (1998), 214235.
• [22] S. Williams, Notes on renewal systems, Proc. Amer. Math. Soc., 110 (1990), 851-853.
• [23] S. Wolfram, A new kind of science, Wolfram Media, Inc., Champaign, IL, 2002.