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

DOI10.1007/978-3-030-68195-1_25MaRDI QIDQ2232292OpenAlexFDO

Authors 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)

Recommendations

• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• The state complexity of alternating automata
• Completely distinguishable automata and the set of synchronizing words
• The state complexity of permutations on finite languages over binary alphabets
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Complexity of problems concerning reset words for cyclic and Eulerian automata
• Complexity of problems concerning reset words for cyclic and Eulerian automata
• Synchronizing automata over nested words
• Synchronizing automata over nested words
• State complexity of partial word finite automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3605922 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• scientific article; zbMATH DE number 3266647 (Why is no real title available?)
• A characterization of completely reachable automata
• Completely reachable automata
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• Hardly reachable subsets and completely reachable automata with 1-deficient words
• Les automates circulaires biaisés vérifient la conjecture de Černý
• Primitive digraphs with large exponents and slowly synchronizing automata
• Reset complexity of ideal languages over a binary alphabet
• Reset complexity of ideal languages over a binary alphabet
• Slowly synchronizing automata and digraphs
• Synchronizing Automata and the Černý Conjecture
• The Černý conjecture and 1-contracting automata

Cited in

(7)

• 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
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• Reset complexity and completely reachable automata with simple idempotents
• Completely distinguishable automata and the set of synchronizing words
• Sync-maximal permutation groups equal primitive permutation groups
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees

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

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