Birecurrent sets

DOI10.1142/S0218196718500285MaRDI QIDQ4576007zbMATH OpenOpenAlexFDO

Authors Francesco Dolce, Dominique Perrin, Christophe Reutenauer, Giuseppina Rindone, Antonio Restivo

Publication date 12 July 2018

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.10081

zbMATH Keywords

regular languageprefix codeformal seriesfinite automatonbifix coderecurrent setbirecurrent set

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: A set is called recurrent if its minimal automaton is strongly connected and birecurrent if it is recurrent as well as its reversal. We prove a series of results concerning birecurrent sets. It is already known that any birecurrent set is completely reducible (that is, such that the minimal representation of its characteristic series is completely reducible). The main result of this paper characterizes completely reducible sets as linear combinations of birecurrent sets

Recommendations

• Sets that force recurrence
• A note on recurrent sets
• scientific article; zbMATH DE number 1261890
• Publication:4333077
• scientific article; zbMATH DE number 169113
• Almost semirecursive sets
• scientific article; zbMATH DE number 3959401
• scientific article; zbMATH DE number 3859104
• Limited Sets and Bibasic Sequences
• On automata recognizing birecurrent sets

Cites work

• scientific article; zbMATH DE number 3905865 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• Codes asynchrones
• Completely reducible sets
• Elements of automata theory. Translated from the French by Reuben Thomas
• Inference of Reversible Languages
• Noncommutative rational series with applications
• On a Special Class of Recurrent Events
• On automata recognizing birecurrent sets
• SYNCHRONIZATION AND DECOMPOSABILITY FOR A FAMILY OF CODES
• Semisimplicity of the algebra associated to a biprefix code
• The \(\mathfrak q\)-theory of finite semigroups.
• Une topologie du monoide libre

Cited in

(5)

• A profinite approach to complete bifix decodings of recurrent languages
• Bisections reconnaissables
• On automata recognizing birecurrent sets
• Completely reducible sets
• scientific article; zbMATH DE number 3934415 (Why is no real title available?)

This page was built for publication: Birecurrent sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4576007)