Complexity of road coloring with prescribed reset words

DOI10.1016/j.jcss.2016.05.009zbMath1425.68236arXiv1412.0799OpenAlexW2467775307MaRDI QIDQ2424693

Vojtěch Vorel, Adam Roman

Publication date: 25 June 2019

Published in: Journal of Computer and System Sciences, Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.0799

zbMATH Keywords

synchronizing wordreset wordsynchronizing automataČerný conjecturealgorithms on automata and wordsroad-coloring problemroad-coloring theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Coloring of graphs and hypergraphs (05C15)

Related Items (8)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ On the Number of Synchronizing Colorings of Digraphs ⋮ Special issue: Selected papers of the 9th international conference on language and automata theory and applications, LATA 2015 ⋮ Synchronizing sequences for road colored digraphs ⋮ Ideal separation and general theorems for constrained synchronization and their application to small constraint automata ⋮ Constrained synchronization and commutativity ⋮ Černý's conjecture and the road colouring problem

Uses Software

• TESTAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semigroups and the generalized road coloring problem
• The road coloring problem
• Synchronizing automata preserving a chain of partial orders
• Synchronizing finite automata with short reset words
• Equivalence of topological Markov shifts
• A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
• Computing the shortest reset words of synchronizing automata
• A quadratic algorithm for road coloring
• P–NP Threshold for Synchronizing Road Coloring
• Strong Inapproximability of the Shortest Reset Word
• On the Number of Synchronizing Colorings of Digraphs
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• An Algorithm for Road Coloring
• Reset Sequences for Monotonic Automata
• A Multivariate Analysis of Some DFA Problems
• The complexity of satisfiability problems
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture

This page was built for publication: Complexity of road coloring with prescribed reset words