A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata

DOI10.1007/978-3-642-02737-6_6zbMath1217.68122OpenAlexW2149252886MaRDI QIDQ3637215

Dominique Perrin, Marie-Pierre Béal

Publication date: 7 July 2009

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02737-6_6

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Prefix, length-variable, comma-free codes (94A45)

Related Items (6)

ON A CONJECTURE BY CARPI AND D'ALESSANDRO ⋮ The Synchronization Problem for Locally Strongly Transitive Automata ⋮ On incomplete and synchronizing finite sets ⋮ The Černý conjecture for one-cluster automata with prime length cycle ⋮ Algebraic synchronization criterion and computing reset words ⋮ Černý's conjecture and the road colouring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The road coloring problem
• Synchronizing Automata Preserving a Chain of Partial Orders
• The Synchronization Problem for Strongly Transitive Automata
• Synchronizing Automata and the Černý Conjecture
• Almost all complete binary prefix codes have a self-synchronizing string
• Shortest Synchronizing Strings for Huffman Codes
• On two Combinatorial Problems Arising from Automata Theory
• Synchronization of Some DFA
• On synchronizing prefix codes

This page was built for publication: A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata