The road coloring problem
From MaRDI portal
Recommendations
Cites work
- A min-max theorem about the road coloring conjecture
- A note on the road-coloring conjecture
- An Introduction to Symbolic Dynamics and Coding
- Cycles of relatively prime length and the road coloring problem
- Equivalence of topological Markov shifts
- scientific article; zbMATH DE number 1185607 (Why is no real title available?)
- scientific article; zbMATH DE number 177164 (Why is no real title available?)
- scientific article; zbMATH DE number 1346363 (Why is no real title available?)
- scientific article; zbMATH DE number 1551726 (Why is no real title available?)
- scientific article; zbMATH DE number 2087221 (Why is no real title available?)
- scientific article; zbMATH DE number 1834666 (Why is no real title available?)
- Notable trends concerning the synchronization of graphs and automata
- On the Road Coloring Problem
- On two Combinatorial Problems Arising from Automata Theory
- Similarity of automorphisms of the torus
- The road-colouring problem
Cited in
(61)- Synchronizing finite automata on Eulerian digraphs.
- In memoriam: Roy Adler (1931--2016) and the lasting impact of his work
- An algorithm for road coloring
- Independent sets of words and the synchronization problem
- The NP-completeness of the road coloring problem
- Černý's conjecture and the road colouring problem
- Computational complexity of synchronization under sparse regular constraints
- Synchronizing sequences for road colored digraphs
- A multi-parameter analysis of hard problems on deterministic finite automata
- Structure of free semigroupoid algebras
- A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
- A quadratic algorithm for road coloring
- On the probability of being synchronizable
- On the synchronizing probability function and the triple rendezvous time for synchronizing automata
- Completely reachable automata
- P-NP threshold for synchronizing road coloring
- Groups and semigroups defined by colorings of synchronizing 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
- An algorithm for road coloring
- Labeling semi group of an automaton and road coloring conjecture
- The Synchronization Problem for Locally Strongly Transitive Automata
- Decision Version of the Road Coloring Problem Is NP-Complete
- Synchronizing Automata and the Černý Conjecture
- A partially synchronizing coloring
- A min-max theorem about the road coloring conjecture
- On the hybrid Černý-road coloring problem and Hamiltonian paths
- A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
- Primitive digraphs with large exponents and slowly synchronizing automata
- scientific article; zbMATH DE number 1185607 (Why is no real title available?)
- scientific article; zbMATH DE number 177164 (Why is no real title available?)
- Sets of nonnegative matrices without positive products
- scientific article; zbMATH DE number 1551726 (Why is no real title available?)
- On synchronizing colorings and the eigenvectors of digraphs
- scientific article; zbMATH DE number 2087221 (Why is no real title available?)
- All finite transitive graphs admit a self-adjoint free semigroupoid algebra
- Attainable values of reset thresholds
- A note on polynomial approximation of synchronizing optimal coloring
- On incomplete and synchronizing finite sets
- Synchronised automata
- Synchronization of Eulerian automaton.
- Synchronization and stability of finite automata
- Synchronizing almost-group automata
- Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach
- Cycles of relatively prime length and the road coloring problem
- Completely distinguishable automata and the set of synchronizing words
- Resolution of sigma-fields for multiparticle finite-state action evolutions with infinite past
- 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
- Colouring solutions of the ice problem
- The further chameleon groups of Richard Thompson and Graham Higman: Automorphisms via dynamics for the Higman-Thompson groups~\(G_{n,r}\)
- This game is not going to analyze itself
- The complexity of computing the period and the exponent of a digraph
- A note on the rank of semigroups.
- The Černý conjecture for one-cluster automata with prime length cycle
- Completely distinguishable automata and the set of synchronizing words
- The hereditariness problem for the Černý conjecture
- Random walk in a finite directed graph subject to a road coloring
- A vector space approach to the road coloring problem
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)
