The road coloring problem
From MaRDI portal
Publication:731355
DOI10.1007/s11856-009-0062-5zbMath1175.05058OpenAlexW2015970678WikidataQ29393812 ScholiaQ29393812MaRDI QIDQ731355
Publication date: 2 October 2009
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11856-009-0062-5
road coloring problemsynchronizing coloringdeterministic finite automatondeterministic automatondirected finite strongly connected graphsynchromizing word
Combinatorics on words (68R15) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)
Related Items (42)
Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ A vector space approach to the road coloring problem ⋮ The Synchronization Problem for Locally Strongly Transitive Automata ⋮ P(l)aying for Synchronization ⋮ Reset Thresholds of Automata with Two Cycle Lengths ⋮ Groups and semigroups defined by colorings of synchronizing automata ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Approximating the minimum length of synchronizing words is hard ⋮ An algorithm for road coloring ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ Resolution of sigma-fields for multiparticle finite-state action evolutions with infinite past ⋮ Complexity of road coloring with prescribed reset words ⋮ Synchronizing sequences for road colored digraphs ⋮ Normalish Amenable Subgroups of the R. Thompson Groups ⋮ The road problem and homomorphisms of directed graphs ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ New characterizations of primitive permutation groups with applications to synchronizing automata ⋮ The NP-completeness of the road coloring problem ⋮ Sets of nonnegative matrices without positive products ⋮ The generalized road coloring problem and periodic digraphs ⋮ In memoriam: Roy Adler (1931--2016) and the lasting impact of his work ⋮ A quadratic algorithm for road coloring ⋮ Synchronizing Automata and the Černý Conjecture ⋮ On incomplete and synchronizing finite sets ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ A note on the rank of semigroups. ⋮ The Černý conjecture for one-cluster automata with prime length cycle ⋮ On the Probability of Being Synchronizable ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Random walk in a finite directed graph subject to a road coloring ⋮ All finite transitive graphs admit a self-adjoint free semigroupoid algebra ⋮ A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA ⋮ A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata ⋮ Realization of an Ergodic Markov Chain as a Random Walk Subject to a Synchronizing Road Coloring ⋮ Completely Reachable Automata ⋮ Černý's conjecture and the road colouring problem ⋮ Structure of free semigroupoid algebras ⋮ Attainable Values of Reset Thresholds ⋮ Unnamed Item ⋮ Synchronizing Almost-Group Automata ⋮ A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
Cites Work
- The road-colouring problem
- Equivalence of topological Markov shifts
- Notable trends concerning the synchronization of graphs and automata
- On two Combinatorial Problems Arising from Automata Theory
- On the Road Coloring Problem
- An Introduction to Symbolic Dynamics and Coding
- Similarity of automorphisms of the torus
- Cycles of relatively prime length and the road coloring problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The road coloring problem
