Completely reachable automata
From MaRDI portal
Abstract: We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word.
Recommendations
Cites work
- Classical finite transformation semigroups. An introduction.
- Classification of L-cross-sections of the finite symmetric semigroup up to isomorphism
- Complexity Analysis: Transformation Monoids of Finite Automata
- Equivalence of topological Markov shifts
- scientific article; zbMATH DE number 3722702 (Why is no real title available?)
- scientific article; zbMATH DE number 6438650 (Why is no real title available?)
- Primitive digraphs with large exponents and slowly synchronizing automata
- RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
- Synchronizing Automata and the Černý Conjecture
- Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages
- The road coloring problem
- Upper bound on syntactic complexity of suffix-free languages
Cited in
(25)- A characterization of completely reachable automata
- On completely reachable automata and subset reachability
- Sync-maximal permutation groups equal primitive permutation groups
- Reset complexity and completely reachable automata with simple idempotents
- 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
- scientific article; zbMATH DE number 512840 (Why is no real title available?)
- The length of subset reachability in nondeterministic automata
- Complexity of preimage problems for deterministic finite automata
- Reset complexity of ideal languages over a binary alphabet
- On the interplay between Černý and Babai's conjectures
- A characterization of totally compatible automata
- Completely distinguishable automata and the set of synchronizing words
- scientific article; zbMATH DE number 7770050 (Why is no real title available?)
- Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
- Binary completely reachable automata
- Reset thresholds of transformation monoids
- Subset mapping problems in solvable automata
- Don's conjecture for binary completely reachable automata: an approach and its limitations
- \(\mathscr{R}\)-cross-sections of the monoid of order-preserving transformations on a finite chain
- Completely reachable almost group automata
- Around Don's conjecture for binary completely reachable automata
- Completely distinguishable automata and the set of synchronizing words
- A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group
This page was built for publication: Completely reachable automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829965)
