Birecurrent sets

DOI10.1142/S0218196718500285zbMATH Open1395.68166arXiv1703.10081OpenAlexW2795834488MaRDI QIDQ4576007FDOQ4576007

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)

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

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

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
• scientific article
• Limited Sets and Bibasic Sequences
• On automata recognizing birecurrent sets

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)

Cites Work

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

Cited In (5)

• Bisections reconnaissables
• On automata recognizing birecurrent sets
• Completely reducible sets
• Title not available (Why is that?)
• A profinite approach to complete bifix decodings of recurrent languages

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)