Strong Inapproximability of the Shortest Reset Word

DOI10.1007/978-3-662-48057-1_19zbMath1466.68051arXiv1408.5248OpenAlexW1794931121MaRDI QIDQ2946340

Damian Straszak, Paweł Gawrychowski

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ Complexity of road coloring with prescribed reset words ⋮ Unnamed Item ⋮ Preimage problems for deterministic finite automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ Algebraic synchronization criterion and computing reset words ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Černý's conjecture and the road colouring problem ⋮ Attainable Values of Reset Thresholds ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata ⋮ The Synchronizing Probability Function for Primitive Sets of Matrices

Cites Work

• Unnamed Item
• Unnamed Item
• The Černý conjecture for one-cluster automata with prime length cycle
• Reset words for commutative and solvable automata
• Synchronizing finite automata on Eulerian digraphs.
• Approximating the minimum length of synchronizing words is hard
• Synchronizing generalized monotonic automata
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Approximating Minimum Reset Sequences
• Proof verification and the hardness of approximation problems
• A threshold of ln n for approximating set cover
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• The Complexity of Finding Reset Words in Finite Automata
• On two Combinatorial Problems Arising from Automata Theory
• Probabilistic checking of proofs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Computational Complexity