Representation of (Left) Ideal Regular Languages by Synchronizing Automata

DOI10.1007/978-3-319-20297-6_21zbMath1465.68162arXiv1412.6767OpenAlexW1875355491MaRDI QIDQ3194726

Marina Maslennikova, Emanuele Rodaro

Publication date: 20 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

decompositionreset wordstrongly connected automatonsynchronizing automatonideal languagereset complexityreset left regular

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items

Strongly connected synchronizing automata and the language of minimal reset words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ideal regular languages and strongly connected synchronizing automata
• Synchronizing automata with finitely many minimal synchronizing words
• On deterministic finite automata and syntactic monoid size
• Synchronization and simplification
• Synchronizing automata preserving a chain of partial orders
• The structure of reflexive regular splicing languages via Schützenberger constants
• Finitely Generated Ideal Languages and Synchronizing Automata
• Regular Ideal Languages and Synchronizing Automata
• Principal Ideal Languages and Synchronizing Automata
• Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete
• Synchronizing Automata and the Černý Conjecture
• Complexity of Checking Whether Two Automata Are Synchronized by the Same Language