Approximating the minimum length of synchronizing words is hard

DOI10.1007/s00224-013-9511-yzbMath1380.68247arXiv0909.3787OpenAlexW1829425890MaRDI QIDQ1678749

Mikhail V. Berlinkov

Publication date: 7 November 2017

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

polynomial-time approximationsynchronizing automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (18)

Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Approximating the minimum length of synchronizing words is hard ⋮ Strong Inapproximability of the Shortest Reset Word ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ Unnamed Item ⋮ Complexity of problems concerning reset words for cyclic and Eulerian automata ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Algebraic synchronization criterion and computing reset words ⋮ Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata ⋮ Experimental Study of the Shortest Reset Word of Random Automata ⋮ Approximating Minimum Reset Sequences ⋮ Slowly synchronizing automata with fixed alphabet size ⋮ Semicomputable points in Euclidean spaces ⋮ Černý's conjecture and the road colouring problem ⋮ Unnamed Item ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Computing the shortest reset words of synchronizing automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of problems concerning reset words for cyclic and Eulerian automata
• The road coloring problem
• Synchronizing finite automata with short reset words
• Equivalence of topological Markov shifts
• Approximating the minimum length of synchronizing words is hard
• Composition sequences for functions over a finite domain.
• The NP-completeness of the road coloring problem
• Synchronization of Automata with One Undefined or Ambiguous Transition
• Approximating Minimum Reset Sequences
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA
• The Complexity of Finding Reset Words in Finite Automata
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS

This page was built for publication: Approximating the minimum length of synchronizing words is hard