Reset complexity and completely reachable automata with simple idempotents

DOI10.1007/978-3-031-13257-5_7OpenAlexW4297974497MaRDI QIDQ2112183

Stefan Hoffmann

Publication date: 18 January 2023

Full work available at URL: https://doi.org/10.1007/978-3-031-13257-5_7

zbMATH Keywords

synchronizationfinite automataset of synchronizing wordsautomata with simple idempotentscompletely reachable automatasync-maximal automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Černý conjecture and 1-contracting automata
• Ideal regular languages and strongly connected synchronizing automata
• Groups synchronizing a transformation of non-uniform kernel
• A characterization of completely reachable automata
• Polynomial complete problems in automata theory
• Černý's conjecture and the road colouring problem
• Sync-maximal permutation groups equal primitive permutation groups
• Preimage problems for deterministic finite automata
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Relationships between nondeterministic and deterministic tape complexities
• Completely Reachable Automata
• Finitely Generated Ideal Languages and Synchronizing Automata
• Reset Complexity of Ideal Languages Over a Binary Alphabet
• An improvement to a recent upper bound for synchronizing words of finite automata
• Estimation of the length of reset words for automata with simple idempotents

This page was built for publication: Reset complexity and completely reachable automata with simple idempotents