A lower bound for the length of the shortest carefully synchronizing words

DOI10.3103/S1066369X10010056zbMath1184.68321OpenAlexW2054252811MaRDI QIDQ845082

Pavel Martyugin

Publication date: 5 February 2010

Published in: Russian Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s1066369x10010056

zbMATH Keywords

finite automatonsynchronizabilitypartial finite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (10)

Using SAT solvers for synchronization issues in non-deterministic automata ⋮ Synchronization of Automata with One Undefined or Ambiguous Transition ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Careful synchronization of partial deterministic finite automata ⋮ Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata ⋮ On the smallest synchronizing terms of finite tree automata ⋮ Lower Bounds for Synchronizing Word Lengths in Partial Automata ⋮ Preset Distinguishing Sequences and Diameter of Transformation Semigroups ⋮ Subset Synchronization and Careful Synchronization of Binary Finite Automata ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata

Cites Work

• Synchronizing finite automata on Eulerian digraphs.
• Reset Sequences for Monotonic Automata
• On two Combinatorial Problems Arising from Automata Theory
• Algebraic Theory of Automata and Languages
• Theory Is Forever

This page was built for publication: A lower bound for the length of the shortest carefully synchronizing words