No Access

COMPLETELY REDUCIBLE SETS

DOMINIQUE PERRIN

LIGM, Université Paris-Est, France

https://doi.org/10.1142/S0218196713400158Cited by:5 (Source: Crossref)

Abstract

We study the family of rational sets of words, called completely reducible and which are such that the syntactic representation of their characteristic series is completely reducible. This family contains, by a result of Reutenauer, the submonoids generated by bifix codes and, by a result of Berstel and Reutenauer, the cyclic sets. We study the closure properties of this family. We prove a result on linear representations of monoids which gives a generalization of the result concerning the complete reducibility of the submonoid generated by a bifix code to sets called birecurrent. We also give a new proof of the result concerning cyclic sets.

Dedicated to Christophe Reutenauer on the occasion of his 60th birthday

Keywords:

AMSC: 20M30, 68Q45

References

J. Almeidaet al., Trans. Amer. Math. Soc. 361(3), 1429 (2009). Crossref, Web of Science, Google Scholar
M.-P. Béal, RAIRO Inform. Théor. Appl. 29(2), 85 (1995). Crossref, Web of Science, Google Scholar
M.-P. Béal, O. Carton and C. Reutenauer, Cyclic languages and strongly cyclic languages, STACS 961046, Lecture Notes in Computer Science (Springer, Berlin, 1996) pp. 49–59. Google Scholar
J. Berstel and D. Perrin , Theory of Codes ( Academic Press , 1985 ) . Google Scholar
J. Berstel , D. Perrin and C. Reutenauer , Codes and Automata ( Cambridge University Press , 2009 ) . Crossref, Google Scholar
J. Berstel and C. Reutenauer, Trans. Amer. Math. Soc. 321(2), 533 (1990). Crossref, Web of Science, Google Scholar
J. Berstel and C. Reutenauer , Noncommutative Rational Series with Applications , Encyclopedia of Mathematics and its Applications 137 ( Cambridge University Press , Cambridge , 2011 ) . Google Scholar
A. H. Clifford and G. B. Preston , The Algebraic Theory of Semigroups , Mathematical Surveys I ( American Mathematical Society , Providence, RI , 1961 ) . Crossref, Google Scholar
S. Eilenberg , Automata, Languages, and Machines , Pure and Applied Mathematics 58 ( Academic Press , New York , 1974 ) . Google Scholar
J. A. Green , Polynomial Representations of GLn , Lecture Notes in Mathematics 830 ( Springer , Berlin , 2007 ) . Google Scholar
G. Lallement , Semigroups and Combinatorial Applications , Pure and Applied Mathematics ( Wiley , New York , 1979 ) . Google Scholar
S. Lang , Algebra , 3rd edn. , Graduate Texts in Mathematics 211 ( Springer-Verlag , New York , 2002 ) . Crossref, Google Scholar
D. A. Lind and B. H. Marcus , An Introduction to Symbolic Dynamics and Coding ( Cambridge University Press , 1995 ) . Crossref, Google Scholar
D. B. McAlister , J. Algebra 22 , 183 ( 1972 ) . Crossref, Web of Science, Google Scholar
C. Reutenauer, J. Algebra 66(2), 448 (1980). Crossref, Web of Science, Google Scholar
C. Reutenauer , Semigroup Forum 23 , 327 ( 1981 ) . Crossref, Web of Science, Google Scholar
J. Rhodes , J. Combin. Theory 6 , 67 ( 1969 ) . Crossref, Google Scholar
B. Steinberg, personal communication (2013) . Google Scholar