Černý's conjecture and the road colouring problem
type: Item
instance of: scholarly article
title: Černý's conjecture and the road colouring problem
author: Jarkko Kari
author: M. V. Volkov
publication date: 2022-02-04T00:00:00Z
review text: Summary: For the entire collection see [Zbl 1470.68001].
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7469513
zbMATH Keywords: sychronising automata
describes a project that uses: COMPAS
MaRDI profile type: Publication
cites work: Equivalence of topological Markov shifts
cites work: Q5208366
cites work: Approximation of Reset Thresholds with Greedy Algorithms
cites work: A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
cites work: A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
cites work: A quadratic algorithm for road coloring
cites work: Approximating the minimum length of synchronizing words is hard
cites work: On Two Algorithmic Problems about Synchronizing Automata
cites work: On the Probability of Being Synchronizable
cites work: Algebraic synchronization criterion and computing reset words
cites work: Q3653240
cites work: Q4794042
cites work: Q4818810
cites work: Dixon's theorem and random synchronization
cites work: On the characterization of statistically synchronizable variable-length codes
cites work: Cycles of relatively prime length and the road coloring problem
cites work: The Synchronization Problem for Locally Strongly Transitive Automata
cites work: On the Hybrid Černý-Road Coloring Problem and Hamiltonian Paths
cites work: Q5629545
cites work: The complexity of oblivious plans for orienting and distinguishing polygonal parts
cites work: COMPAS - A Computing Package for Synchronization
cites work: Q3651735
cites work: A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
cites work: DFAs and PFAs with long shortest synchronizing word length
cites work: The spectrum of dynamical systems arising from substitutions of constant length
cites work: Finding DFAs with Maximal Shortest Synchronizing Word Length
cites work: Gaps in the exponent set of primitive matrices
cites work: Attainable Values of Reset Thresholds
cites work: Reset Sequences for Monotonic Automata
cites work: An extremal problem for two families of sets
cites work: Computing modular coincidences for substitution tilings and point sets
cites work: On the Road Coloring Problem
cites work: Q4198056
cites work: Strong Inapproximability of the Shortest Reset Word
cites work: Approximating Minimum Reset Sequences
cites work: State-identification experiments in finite automata
cites work: Q5519562
cites work: Orienting polygonal parts without sensors
cites work: On the Interplay Between Černý and Babai’s Conjectures
cites work: Q5249242
cites work: RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
cites work: Dynamics of the independence number and automata synchronization
cites work: On the Number of Synchronizing Colorings of Digraphs
cites work: Q3838420
cites work: A counter example to a conjecture concerning synchronizing words in finite automata
cites work: Q5422239
cites work: Synchronizing finite automata on Eulerian digraphs.
cites work: Computing the shortest reset words of synchronizing automata
cites work: Experiments with Synchronizing Automata
cites work: Generating Small Automata and the Černý Conjecture
cites work: Synchronizing Automata with Extremal Properties
cites work: In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
cites work: Q5684962
cites work: Establishing certain bounds concerning finite automata
cites work: Automata Studies. (AM-34)
cites work: The Cerny Conjecture Holds with High Probability
cites work: The road-colouring problem
cites work: The Complexity of Finding Reset Words in Finite Automata
cites work: Q4298260
cites work: The complexity of facets (and some facets of complexity)
cites work: Q4037012
cites work: Q4171566
cites work: On two Combinatorial Problems Arising from Automata Theory
cites work: Q5541339
cites work: Q5704414
cites work: Genetic Algorithm for Synchronization
cites work: Synchronizing finite automata with short reset words
cites work: The NP-completeness of the road coloring problem

Černý's conjecture and the road colouring problem (cites work)
cites work: A complete solution to the complexity of synchronizing road coloring for non-binary alphabets

Černý's conjecture and the road colouring problem (cites work)
cites work: Almost optimal bound of recurrent word length for regular automata

Černý's conjecture and the road colouring problem (cites work)
cites work: Q4864787

Černý's conjecture and the road colouring problem (cites work)
cites work: Estimation of the length of reset words for automata with simple idempotents

Černý's conjecture and the road colouring problem (cites work)
cites work: Composition sequences for functions over a finite domain.

Černý's conjecture and the road colouring problem (cites work)
cites work: A taxonomy of complexity classes of functions

Černý's conjecture and the road colouring problem (cites work)
cites work: Experimental Study of the Shortest Reset Word of Random Automata

Černý's conjecture and the road colouring problem (cites work)
cites work: Q5414550

Černý's conjecture and the road colouring problem (cites work)
cites work: The Averaging Trick and the Černý Conjecture

Černý's conjecture and the road colouring problem (cites work)
cites work: The Černý conjecture for one-cluster automata with prime length cycle

Černý's conjecture and the road colouring problem (cites work)
cites work: Q3304155

Černý's conjecture and the road colouring problem (cites work)
cites work: An Extremal Series of Eulerian Synchronizing Automata

Černý's conjecture and the road colouring problem (cites work)
cites work: An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture

Černý's conjecture and the road colouring problem (cites work)
cites work: The road coloring problem

Černý's conjecture and the road colouring problem (cites work)
cites work: Modifying the Upper Bound on the Length of Minimal Synchronizing Word

Černý's conjecture and the road colouring problem (cites work)
cites work: Synchronizing Automata and the Černý Conjecture

Černý's conjecture and the road colouring problem (cites work)
cites work: Complexity of road coloring with prescribed reset words

Černý's conjecture and the road colouring problem (cites work)
cites work: Q5249241

Černý's conjecture and the road colouring problem (cites work)
cites work: Unzerlegbare, nicht negative Matrizen

Černý's conjecture and the road colouring problem (cites work)
cites work: Synchronizing random automata on a 4-letter alphabet

Černý's conjecture and the road colouring problem (DOI)
DOI: 10.4171/AUTOMATA-1/15