Reset words for commutative and solvable automata

DOI10.1016/S0304-3975(96)00136-3zbMath0903.68122MaRDI QIDQ1392028

Igor Rystsov

Publication date: 23 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite automatonreset word

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (30)

Synchronizing automata preserving a chain of partial orders ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Unnamed Item ⋮ The annulation threshold for partially monotonic automata ⋮ ON A CONJECTURE BY CARPI AND D'ALESSANDRO ⋮ THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Constrained synchronization for monotonic and solvable automata and automata with simple idempotents ⋮ Strong Inapproximability of the Shortest Reset Word ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Synchronizing automata with coinciding cycles ⋮ Synchronizing Automata Preserving a Chain of Partial Orders ⋮ Slowly synchronizing automata with zero and noncomplete sets ⋮ Unnamed Item ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ Algorithms for media ⋮ Shortest directing words of nondeterministic directable automata ⋮ A series of slowly synchronizing automata with a zero state over a small alphabet ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number ⋮ The Černý conjecture for one-cluster automata with prime length cycle ⋮ Genetic Algorithm for Synchronization ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Matrix Mortality and the Černý-Pin Conjecture ⋮ Attainable Values of Reset Thresholds ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ The Synchronizing Probability Function for Primitive Sets of Matrices ⋮ Composition sequences for functions over a finite domain. ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work

• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Reset Sequences for Monotonic Automata
• The Theory of Definite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reset words for commutative and solvable automata