Černý's conjecture and the road colouring problem
From MaRDI portal
Publication:2074216
DOI10.4171/Automata-1/15MaRDI QIDQ2074216
Jarkko Kari, Mikhail V. Volkov
Publication date: 4 February 2022
Related Items (15)
Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ Constrained synchronization for monotonic and solvable automata and automata with simple idempotents ⋮ Careful synchronization of partial deterministic finite automata ⋮ Synchronizing times for \(k\)-sets in automata ⋮ Synchronizing Automata with Extremal Properties ⋮ On the Number of Synchronizing Colorings of Digraphs ⋮ Synchronization of Parikh automata ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ 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 ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Algebraic synchronization criterion and computing reset words ⋮ Attainable Values of Reset Thresholds ⋮ Reset complexity and completely reachable automata with simple idempotents
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Synchronizing random automata on a 4-letter alphabet
- Dixon's theorem and random synchronization
- Orienting polygonal parts without sensors
- The Černý conjecture for one-cluster automata with prime length cycle
- The road coloring problem
- Computing modular coincidences for substitution tilings and point sets
- Synchronizing finite automata with short reset words
- The complexity of facets (and some facets of complexity)
- The road-colouring problem
- An extremal problem for two families of sets
- Equivalence of topological Markov shifts
- A taxonomy of complexity classes of functions
- Synchronizing finite automata on Eulerian digraphs.
- Dynamics of the independence number and automata synchronization
- Approximating the minimum length of synchronizing words is hard
- Establishing certain bounds concerning finite automata
- Composition sequences for functions over a finite domain.
- The complexity of oblivious plans for orienting and distinguishing polygonal parts
- Almost optimal bound of recurrent word length for regular automata
- The NP-completeness of the road coloring problem
- Algebraic synchronization criterion and computing reset words
- A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
- Computing the shortest reset words of synchronizing automata
- Gaps in the exponent set of primitive matrices
- DFAs and PFAs with long shortest synchronizing word length
- Complexity of road coloring with prescribed reset words
- A quadratic algorithm for road coloring
- Unzerlegbare, nicht negative Matrizen
- On the Probability of Being Synchronizable
- An Extremal Series of Eulerian Synchronizing Automata
- Experiments with Synchronizing Automata
- On Two Algorithmic Problems about Synchronizing Automata
- Strong Inapproximability of the Shortest Reset Word
- Synchronizing Automata with Extremal Properties
- On the Number of Synchronizing Colorings of Digraphs
- A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
- In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
- COMPAS - A Computing Package for Synchronization
- Approximating Minimum Reset Sequences
- A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
- Modifying the Upper Bound on the Length of Minimal Synchronizing Word
- The Synchronization Problem for Locally Strongly Transitive Automata
- Automata Studies. (AM-34)
- Reset Sequences for Monotonic Automata
- Synchronizing Automata and the Černý Conjecture
- On the Hybrid Černý-Road Coloring Problem and Hamiltonian Paths
- The Averaging Trick and the Černý Conjecture
- The Complexity of Finding Reset Words in Finite Automata
- Genetic Algorithm for Synchronization
- A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
- On two Combinatorial Problems Arising from Automata Theory
- On the characterization of statistically synchronizable variable-length codes
- On the Road Coloring Problem
- The spectrum of dynamical systems arising from substitutions of constant length
- RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
- Approximation of Reset Thresholds with Greedy Algorithms
- Attainable Values of Reset Thresholds
- Experimental Study of the Shortest Reset Word of Random Automata
- The Cerny Conjecture Holds with High Probability
- Generating Small Automata and the Černý Conjecture
- State-identification experiments in finite automata
- On the Interplay Between Černý and Babai’s Conjectures
- Finding DFAs with Maximal Shortest Synchronizing Word Length
- An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
- Cycles of relatively prime length and the road coloring problem
- Estimation of the length of reset words for automata with simple idempotents
This page was built for publication: Černý's conjecture and the road colouring problem
