Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees

DOI10.1142/S0129054123450053arXiv2201.05075OpenAlexW4384522578MaRDI QIDQ6072405

Unnamed Author, E. A. Bondar', Mikhail V. Volkov

Publication date: 13 October 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2201.05075

zbMATH Keywords

treedeterministic finite automatonstrongly connected graphcomplete reachability

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx) Semigroups (20Mxx)

Related Items (3)

Completely distinguishable automata and the set of synchronizing words ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Černý conjecture and 1-contracting automata
• Synchronizing monotonic automata
• The Černý conjecture for one-cluster automata with prime length cycle
• Synchronizing automata preserving a chain of partial orders
• Synchronization
• An extremal problem for two families of sets
• Reset words for commutative and solvable automata
• Synchronizing finite automata on Eulerian digraphs.
• A characterization of completely reachable automata
• Synchronizing generalized monotonic automata
• Černý's conjecture and the road colouring problem
• Reset complexity and completely reachable automata with simple idempotents
• 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
• Between primitive and 2-transitive: synchronization and its friends
• Model-based testing of reactive systems. Advanced lectures.
• Completely Reachable Automata
• THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Modifying the Upper Bound on the Length of Minimal Synchronizing Word
• Combinatorics, Words and Symbolic Dynamics
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• On two Combinatorial Problems Arising from Automata Theory
• Semigroups generated by a group and an idempotent
• Reset Complexity of Ideal Languages Over a Binary Alphabet
• An improvement to a recent upper bound for synchronizing words of finite automata
• On the Interplay Between Černý and Babai’s Conjectures
• COLLAPSING WORDS: A PROGRESS REPORT
• Estimation of the length of reset words for automata with simple idempotents
• Binary completely reachable automata
• Synchronization of finite automata

This page was built for publication: Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees