Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
From MaRDI portal
Abstract: A deterministic finite automaton in which every non-empty set of states occurs as the image of the whole state set under the action of a suitable input word is called completely reachable. We characterize such automata in terms of graphs and trees.
Cites work
- A characterization of completely reachable automata
- A note on a recent attempt to improve the Pin-Frankl bound
- A note on homogeneous experiments with finite automata
- An extremal problem for two families of sets
- An improvement to a recent upper bound for synchronizing words of finite automata
- Between primitive and 2-transitive: synchronization and its friends
- Binary completely reachable automata
- Černý's conjecture and the road colouring problem
- Codes and automata.
- COLLAPSING WORDS: A PROGRESS REPORT
- Combinatorics, Words and Symbolic Dynamics
- Completely reachable automata
- Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
- Estimation of the length of reset words for automata with simple idempotents
- Hardly reachable subsets and completely reachable automata with 1-deficient words
- scientific article; zbMATH DE number 7228447 (Why is no real title available?)
- scientific article; zbMATH DE number 1346363 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 1868895 (Why is no real title available?)
- In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
- Introduction to algorithms.
- Model-based testing of reactive systems. Advanced lectures.
- Modifying the upper bound on the length of minimal synchronizing word
- On the interplay between Černý and Babai's conjectures
- On two Combinatorial Problems Arising from Automata Theory
- Reset complexity and completely reachable automata with simple idempotents
- Reset complexity of ideal languages over a binary alphabet
- Reset Sequences for Monotonic Automata
- Reset words for commutative and solvable automata
- Semigroups generated by a group and an idempotent
- SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
- State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
- Synchronization
- Synchronization of finite automata
- Synchronizing Automata and the Černý Conjecture
- Synchronizing automata preserving a chain of partial orders
- Synchronizing finite automata on Eulerian digraphs.
- Synchronizing generalized monotonic automata
- Synchronizing monotonic automata
- The averaging trick and the Černý conjecture
- The Černý conjecture and 1-contracting automata
- The Černý conjecture for aperiodic automata
- The Černý conjecture for automata respecting intervals of a directed graph
- The Černý conjecture for one-cluster automata with prime length cycle
Cited in
(11)- scientific article; zbMATH DE number 475414 (Why is no real title available?)
- scientific article; zbMATH DE number 1836354 (Why is no real title available?)
- Completely distinguishable automata and the set of synchronizing words
- Interaction graphs of isomorphic automata networks. I: Complete digraph and minimum in-degree
- 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
- Subset mapping problems in solvable automata
- Don's conjecture for binary completely reachable automata: an approach and its limitations
- Completely reachable almost group 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: An Interplay Between Automata, Graphs, and Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072405)
