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

DOI10.3103/S1066369X10010056zbMath1184.68321MaRDI 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 automaton; synchronizability; partial finite automaton

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

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