Completely Reachable Automata
From MaRDI portal
Publication:2829965
DOI10.1007/978-3-319-41114-9_1zbMath1435.68145arXiv1607.00554OpenAlexW2468044850MaRDI QIDQ2829965
E. A. Bondar', Mikhail V. Volkov
Publication date: 9 November 2016
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.00554
PSPACE-completenessdeterministic finite automatonsyntactic complexitytransition monoidcomplete reachability
Related Items (13)
Completely distinguishable automata and the set of synchronizing words ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Binary completely reachable automata ⋮ Unnamed Item ⋮ Preimage problems for deterministic finite automata ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ Complexity of 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 ⋮ Reset Complexity of Ideal Languages Over a Binary Alphabet ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Reset complexity and completely reachable automata with simple idempotents
Cites Work
- Primitive digraphs with large exponents and slowly synchronizing automata
- The road coloring problem
- Classical finite transformation semigroups. An introduction.
- Equivalence of topological Markov shifts
- Complexity Analysis: Transformation Monoids of Finite Automata
- Synchronizing Automata and the Černý Conjecture
- RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
- SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES
- Upper Bound on Syntactic Complexity of Suffix-Free Languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Completely Reachable Automata
