The road coloring problem
From MaRDI portal
Publication:731355
DOI10.1007/S11856-009-0062-5zbMATH Open1175.05058OpenAlexW2015970678WikidataQ29393812 ScholiaQ29393812MaRDI QIDQ731355FDOQ731355
Authors: A. N. Trahtman 
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
Recommendations
deterministic finite automatondeterministic automatondirected finite strongly connected graphroad coloring problemsynchromizing wordsynchronizing coloring
Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Combinatorics on words (68R15)
Cites Work
- An Introduction to Symbolic Dynamics and Coding
- Similarity of automorphisms of the torus
- On two Combinatorial Problems Arising from Automata Theory
- Title not available (Why is that?)
- Equivalence of topological Markov shifts
- Notable trends concerning the synchronization of graphs and automata
- Title not available (Why is that?)
- On the Road Coloring Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A note on the road-coloring conjecture
- The road-colouring problem
- Cycles of relatively prime length and the road coloring problem
- A min-max theorem about the road coloring conjecture
- Title not available (Why is that?)
Cited In (57)
- The further chameleon groups of Richard Thompson and Graham Higman: Automorphisms via dynamics for the Higman-Thompson groups~\(G_{n,r}\)
- Normalish Amenable Subgroups of the R. Thompson Groups
- On synchronizing colorings and the eigenvectors of digraphs
- Synchronizing almost-group automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the hybrid Černý-road coloring problem and Hamiltonian paths
- Independent sets of words and the synchronization problem
- A note on the rank of semigroups.
- Title not available (Why is that?)
- Cycles of relatively prime length and the road coloring problem
- P-NP threshold for synchronizing road coloring
- On the probability of being synchronizable
- A vector space approach to the road coloring problem
- Synchronised automata
- Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach
- Synchronization and stability of finite automata
- Computational complexity of synchronization under sparse regular constraints
- Sets of nonnegative matrices without positive products
- Labeling semi group of an automaton and road coloring conjecture
- 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
- Random walk in a finite directed graph subject to a road coloring
- Attainable values of reset thresholds
- Synchronization of Eulerian automaton.
- The Synchronization Problem for Locally Strongly Transitive Automata
- All finite transitive graphs admit a self-adjoint free semigroupoid algebra
- Structure of free semigroupoid algebras
- An algorithm for road coloring
- A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
- A min-max theorem about the road coloring conjecture
- An algorithm for road coloring
- Groups and semigroups defined by colorings of synchronizing automata.
- Černý's conjecture and the road colouring problem
- Title not available (Why is that?)
- A multi-parameter analysis of hard problems on deterministic finite automata
- Synchronizing finite automata on Eulerian digraphs.
- The Černý conjecture for one-cluster automata with prime length cycle
- A note on polynomial approximation of synchronizing optimal coloring
- The NP-completeness of the road coloring problem
- A partially synchronizing coloring
- Realization of an ergodic Markov chain as a random walk subject to a synchronizing road coloring
- A quadratic upper bound on the size of a synchronizing word in one-cluster automata
- Synchronizing Automata and the Černý Conjecture
- On the synchronizing probability function and the triple rendezvous time for synchronizing automata
- Resolution of sigma-fields for multiparticle finite-state action evolutions with infinite past
- Colouring solutions of the ice problem
- A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
- Synchronizing sequences for road colored digraphs
- Primitive digraphs with large exponents and slowly synchronizing automata
- Decision Version of the Road Coloring Problem Is NP-Complete
- A quadratic algorithm for road coloring
- Completely reachable automata
- Completely distinguishable automata and the set of synchronizing words
- On incomplete and synchronizing finite sets
- In memoriam: Roy Adler (1931--2016) and the lasting impact of his work
This page was built for publication: The road coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q731355)
