State complexity of the set of synchronizing words for circular automata and automata over binary alphabets

DOI10.1007/978-3-030-68195-1_25OpenAlexW3133699300MaRDI QIDQ2232292

Stefan Hoffmann

Publication date: 4 October 2021

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

zbMATH Keywords

synchronizationfinite automatastate complexityset of synchronizing wordscompletely reachable automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Completely distinguishable automata and the set of synchronizing words ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ New characterizations of primitive permutation groups with applications to synchronizing automata ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Reset complexity and completely reachable automata with simple idempotents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Černý conjecture and 1-contracting automata
• Primitive digraphs with large exponents and slowly synchronizing automata
• A characterization of completely reachable automata
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• Reset complexity of ideal languages over a binary alphabet
• Completely Reachable Automata
• Synchronizing Automata and the Černý Conjecture
• Slowly Synchronizing Automata and Digraphs
• Les automates circulaires biaisés vérifient la conjecture de Černý
• Reset Complexity of Ideal Languages Over a Binary Alphabet

This page was built for publication: State complexity of the set of synchronizing words for circular automata and automata over binary alphabets