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

DOI10.3103/S1066369X10010056zbMATH Open1184.68321OpenAlexW2054252811MaRDI QIDQ845082FDOQ845082

Authors 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

synchronizabilityfinite automatonpartial finite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
• Careful synchronization of partial automata with restricted alphabets
• Lower Bound for the Length of Synchronizing Words in Partially-Synchronizing Automata
• Subset synchronization and careful synchronization of binary finite automata
• Modifying the upper bound on the length of minimal synchronizing word

Cites Work

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

Cited In (15)

• Title not available (Why is no real title available?)
• Preset distinguishing sequences and diameter of transformation semigroups
• Title not available (Why is no real title available?)
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Lower bounds for synchronizing word lengths in partial automata
• Lower Bound for the Length of Synchronizing Words in Partially-Synchronizing Automata
• Primitive sets of nonnegative matrices and synchronizing automata
• Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
• Subset synchronization and careful synchronization of binary finite automata
• Careful synchronization of partial deterministic finite automata
• On the smallest synchronizing terms of finite tree automata
• Some results concerning careful synchronization of partial automata and subset synchronization of DFA's
• Synchronization of automata with one undefined or ambiguous transition
• Careful synchronization of partial automata with restricted alphabets
• Using SAT solvers for synchronization issues in non-deterministic automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845082)