The Synchronization Problem for Locally Strongly Transitive Automata

DOI10.1007/978-3-642-03816-7_19MaRDI QIDQ3182926zbMATH OpenOpenAlexFDO

Authors Flavio D'Alessandro, Arturo Carpi

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03816-7_19

zbMATH Keywords

rational seriessynchronizing automatonroad coloring problemČerný conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Independent sets of words and the synchronization problem
• Locally strongly transitive automata in the Černý conjecture and related problems
• The road coloring problem

Cites work

• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1346363 (Why is no real title available?)
• A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
• Almost optimal bound of recurrent word length for regular automata
• An extremal problem for two families of sets
• Equivalence of topological Markov shifts
• On synchronizing unambiguous automata
• Synchronizing Automata and the Černý Conjecture
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• The Synchronization Problem for Strongly Transitive Automata
• The road coloring problem
• The road-colouring problem
• The Černý conjecture for aperiodic automata

Cited in

(7)

• scientific article; zbMATH DE number 1953272 (Why is no real title available?)
• Independent sets of words and the synchronization problem
• Trim Strongly Connected Synchronizing Automata and Ideal Languages
• Černý's conjecture and the road colouring problem
• The Černý conjecture for one-cluster automata with prime length cycle
• Locally strongly transitive automata in the Černý conjecture and related problems
• On incomplete and synchronizing finite sets

This page was built for publication: The Synchronization Problem for Locally Strongly Transitive Automata

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