A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM

DOI10.1142/S0129054102001217zbMath1066.68065OpenAlexW2102353107WikidataQ62045966 ScholiaQ62045966MaRDI QIDQ3021964

Juhani Karhumäki, Jarkko Kari, Karel II Culik

Publication date: 22 June 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054102001217

zbMATH Keywords

synchronizationfinite automataroad coloring problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ A vector space approach to the road coloring problem ⋮ An algorithm for road coloring ⋮ Complexity of road coloring with prescribed reset words ⋮ New characterizations of primitive permutation groups with applications to synchronizing automata ⋮ Černý's conjecture and the road colouring problem

Cites Work

• The road-colouring problem
• Equivalence of topological Markov shifts
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton

This page was built for publication: A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM