No Access

ON THE TRANSITION SEMIGROUPS OF CENTRALLY LABELED RAUZY GRAPHS

CMUP, Departamento de Matemática, Faculdade de Ciências, Universidade do Porto, Rua do Campo Alegre 687, 4169-007 Porto, Portugal

Search for more papers by this author

and

ALFREDO COSTA

CMUC, Department of Mathematics, University of Coimbra, 3001-454 Coimbra, Portugal

Search for more papers by this author

https://doi.org/10.1142/S021819671250018XCited by:4 (Source: Crossref)

Abstract

Rauzy graphs of subshifts are endowed with an automaton structure. For Sturmian subshifts, it is shown that its transition semigroup is the syntactic semigroup of the language recognized by the automaton. An inverse limit of the partial semigroups of nonzero regular elements of their transition semigroups is described. If the subshift is minimal, then this inverse limit is isomorphic, as a partial semigroup, to the -class associated to it in the free pro-aperiodic semigroup.

Keywords:

AMSC: 20M05, 20M07, 20M35, 37B10

References

A. Aberkane, Bull. Belg. Math. Soc. Simon Stevin 8(2), 161 (2001). Web of Science, Google Scholar
A. Aberkane, Theoret. Comput. Sci. 307(1), 31 (2003), DOI: 10.1016/S0304-3975(03)00091-4. Crossref, Web of Science, Google Scholar
J. Almeida , Finite Semigroups and Universal Algebra ( World Scientific , Singapore , 1995 ) . Link, Google Scholar
J. Almeida, RIMS Kokyuroku 1366, 1 (2004). Google Scholar
J. Almeida, Profinite groups associated with weakly primitive substitutions, Fundam. Prikl. Mat. (Fundamental and Applied Mathematics) 11(3) (2005) 13–48 (in Russian); J. Math. Sciences 144(2) (2007) 3881–3903 (in English) . Google Scholar
J. Almeida, Structural Theory of Automata, Semigroups, and Universal Algebra, NATO Science Series II: Mathematics, Physics and Chemistry 207, eds. Valery B. Kudryavtsev and Ivo G. Rosenberg (Springer, 2005) pp. 1–45. Crossref, Google Scholar
J. Almeida and A. Costa, J. Pure Appl. Algebra 213, 605 (2009), DOI: 10.1016/j.jpaa.2008.08.009. Crossref, Web of Science, Google Scholar
J. Almeida and A. Costa, Presentations of Schützenberger groups of minimal subshifts, Technical Report CMUP 2010-1, University of Porto (2010) . Google Scholar
J. Almeida and M. V. Volkov, Int. J. Algebra Comput. 16, 221 (2006). Link, Web of Science, Google Scholar
P. Arnoux and G. Rauzy, Bull. Soc. Math. France 119(2), 199 (1991). Crossref, Web of Science, Google Scholar
J. Berstel, Int. J. Algebra Comput. 12, 371 (2002), DOI: 10.1142/S021819670200095X. Link, Web of Science, Google Scholar
J. Berstel , D. Perrin and Ch. Reutenauer , Codes and Automata , Encyclopedia of Mathematics and its Applications 129 ( Cambridge University Press , Cambridge , 2010 ) . Google Scholar
A. Costa, Int. J. Algebra Comput. 16(4), 629 (2006). Link, Web of Science, Google Scholar
A. Costa and B. Steinberg, Proc. London Math. Soc. 102, 341 (2011), DOI: 10.1112/plms/pdq024. Crossref, Web of Science, Google Scholar
S. Ferenczi, Discrete Math. 206, 145 (1999), DOI: 10.1016/S0012-365X(98)00400-2. Crossref, Web of Science, Google Scholar
N. P. Fogg , Substitutions in Dynamics, Arithmetics and Combinatorics , Lecture Notes in Mathematics 1794 ( Springer-Verlag , Berlin , 2002 ) . Crossref, Google Scholar
A. E. Frid, Discrete Appl. Math. 114(3), 121 (2001), DOI: 10.1016/S0166-218X(00)00365-6. Crossref, Web of Science, Google Scholar
R. P. Hunter, Semigroup Forum 26, 125 (1983), DOI: 10.1007/BF02572826. Crossref, Web of Science, Google Scholar
M. Lothaire , Algebraic Combinatorics on Words ( Cambridge University Press , Cambridge, UK , 2002 ) . Crossref, Google Scholar
J.-J. Pansiot, Automata, Languages and Programming, Lecture Notes in Computer Science 172 (Springer, 1984) pp. 380–389. Crossref, Google Scholar
J.-E. Pin , Varieties of Formal Languages ( Plenum , London , 1986 ) . Crossref, Google Scholar
G. Rauzy, Seminar on Number Theory (Université Bordeaux I, Talence, 1983) p. 16. Google Scholar
P. V. Salimov, On Rauzy graph sequences of infinite words, J. Appl. Indust. Math. (2010) 127–135 (in English); Diskret. Anal. Issled. Oper. 15(5) (2008) 61–75 (Originally published in Russian) . Google Scholar