nach oben

Theory of Computing Systems

Erschienen in:

01.11.2013

Sofic Tree-Shifts

verfasst von: Nathalie Aubrun, Marie-Pierre Béal

Erschienen in: Theory of Computing Systems | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite ranked trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique reduced deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Fischer automaton of the tree-shift. We define the notion of almost of finite type tree-shift which are sofic tree-shifts accepted by a tree automaton which is both deterministic and co-deterministic with a finite delay. It is a meaningful intermediate dynamical class in between irreducible finite type tree-shifts and irreducible sofic tree-shifts. We characterize the Fischer automaton of an almost of finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type. We prove that the Fischer automaton is a topological conjugacy invariant of the underlying irreducible sofic tree-shift.

Vorheriger Artikel A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments

Nächster Artikel A Process Calculus with Finitary Comprehended Terms

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Each prefix of L belongs to L.

i.e. no word is prefix of another one.

Also called a homing pattern or a magic pattern.

Also called the Shannon automaton of the tree-shift. It corresponds to the right Fischer automaton of a sofic shift of sequences.

Aubrun, N., Béal, M.-P.: Decidability of conjugacy of tree-shifts of finite type. In: ICALP’09: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pp. 132–143. Springer, Berlin, Heidelberg (2009) CrossRef

Aubrun, N., Béal, M.-P.: Sofic and almost of finite type tree-shifts. In: CSR. Lecture Notes in Computer Science, vol. 6072, pp. 12–24. Springer, Berlin (2010)

Aubrun, N., Béal, M.-P.: Tree-shifts of finite type. Theor. Comput. Sci. 459, 16–25 (2012) MATHCrossRef

Bates, T., Eilers, S., Pask, D.: Reducibility of covers of AFT shifts. Isr. J. Math. 185, 207–234 (2011) MathSciNetMATHCrossRef

Béal, M.-P., Berstel, J., Eilers, S., Perrin, D.: Symbolic dynamics. Corros. Rev. (2010). arXiv:1006.1265 [cs.FL]

Béal, M.-P., Fiorenzi, F., Perrin, D.: A hierarchy of shift equivalent sofic shifts. Theor. Comput. Sci. 345(2–3), 190–205 (2005) MATHCrossRef

Béal, M.-P., Perrin, D.: Symbolic dynamics and finite automata. In: Handbook of Formal Languages, vol. 2, pp. 463–505. Springer, Berlin (1997) CrossRef

Boyle, M., Kitchens, B., Marcus, B.: A note on minimal covers for sofic systems. Proc. Am. Math. Soc. 95(3), 403–411 (1985) MathSciNetMATHCrossRef

Ceccherini-Silberstein, T., Coornaert, M., Fiorenzi, F., Sunic, Z.: Cellular automata on regular rooted trees. In: CIAA, pp. 101–112 (2012)

10.

Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007). http://www.grappa.univ-lille3.fr/tata

11.

Coven, E., Johnson, A., Jonoska, N., Madden, K.: The symbolic dynamics of multidimensional tiling systems. Ergod. Theory Dyn. Syst. 23(02), 447–460 (2003) MathSciNetMATHCrossRef

12.

Fici, G., Fiorenzi, F.: Topological properties of cellular automata on trees. In: DCM, pp. 255–266 (2012)

13.

Fujiwara, M., Osikawa, M.: Sofic systems and flow equivalence. Math. Rep. Coll. Gen. Educ. Kyushu Univ. 16(1), 17–27 (1987) MathSciNet

14.

Hedlund, G.: Endomorphisms and automorphisms of the shift dynamical system. Theory Comput. Syst. 3(4), 320–375 (1969) MathSciNetMATH

15.

Johnson, A.S.A., Madden, K.M.: The decomposition theorem for two-dimensional shifts of finite type. Proc. Am. Math. Soc. 127(5), 1533–1543 (1999) MathSciNetMATHCrossRef

16.

Jonoska, N., Marcus, B.: Minimal presentations for irreducible sofic shifts. IEEE Trans. Inf. Theory 40(6), 1818–1825 (1994) MathSciNetMATHCrossRef

17.

Kitchens, B.P.: Symbolic Dynamics: One-sided, two-sided and Countable State Markov Shifts. Universitext. Springer, Berlin (1998) MATH

18.

Krieger, W.: On sofic systems. I. Isr. J. Math. 48(4), 305–330 (1984) MathSciNetMATHCrossRef

19.

Lind, D., Schmidt, K.: Symbolic and algebraic dynamical systems. In: Handbook of Dynamical Systems, vol. 1A, pp. 765–812. North-Holland, Amsterdam (2002)

20.

Lind, D.A., Marcus, B.H.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995) MATHCrossRef

21.

Marcus, B.H.: Sofic systems and encoding data. IEEE Trans. Inf. Theory 31(3), 366–377 (1985) MATHCrossRef

22.

Nasu, M.: Textile Systems for Endomorphisms and Automorphisms of the Shift. Am. Math. Soc., Providence (1995)

23.

Neumann, J., Szepietowski, A., Walukiewicz, I.: Complexity of weak acceptance conditions in tree automata. Inf. Process. Lett. 84(4), 181–187 (2002) MathSciNetMATHCrossRef

24.

Perrin, D., Pin, J.: Infinite Words. Elsevier, Boston (2004) MATH

25.

Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009) MATH

26.

Seidl, H.: On the finite degree of ambiguity of finite tree automata. In: Fundamentals of Computation Theory, Szeged, 1989. Lecture Notes in Comput. Sci., vol. 380, pp. 395–404. Springer, New York (1989) CrossRef

27.

Thomas, W.: Automata on infinite objects. In: Handbook of Theoretical Computer Science, vol. B, pp. 133–191. Elsevier, Amsterdam (1990)

28.

Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. III, pp. 389–455. Springer, New York (1997) CrossRef

29.

Verdú-Mas, J., Carrasco, R., Calera-Rubio, J.: Parsing with probabilistic strictly locally testable tree languages. IEEE Trans. Pattern Anal. Mach. Intell. 27(7), 1040–1050 (2005) CrossRef

30.

Williams, R.F.: Classification of subshifts of finite type. In: Recent Advances in Topological Dynamics (Proc. Conf. Topological Dynamics), Yale Univ., New Haven, Conn. Lecture Notes in Math., vol. 318, pp. 281–285. Springer, Berlin (1973) CrossRef

31.

Williams, S.: Covers of non-almost-finite type sofic systems. Proc. Am. Math. Soc. 104(1), 245–252 (1988) MATHCrossRef

Titel: Sofic Tree-Shifts
verfasst von: Nathalie Aubrun
Marie-Pierre Béal
Publikationsdatum: 01.11.2013
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2013
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-013-9456-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2013

Compact DSOP and Partial DSOP Forms

Normalized Range Voting Broadly Resists Control

A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments

Motion Planning with Pulley, Rope, and Baskets

A Process Calculus with Finitary Comprehended Terms

Log-Space Algorithms for Paths and Matchings in k-Trees

Premium Partner