Approximating the minimum length of synchronizing words is hard

2009/09/30 by M. V. Berlinkov · 1 citation
Computer Science · #cs.FL #cs.CC

paper · pdf · doi:10.1007/978-3-642-13182-0_4

12 pages, 1 figure

arxiv created 2009/12/19 · arxiv updated 2015/05/14

Abstract

We prove that, unless P=NP, no polynomial algorithm can approximate the minimum length of \sws for a given \san within a constant factor.

Cited by

• Learning Tree Automata with Term Rewriting

Related

• Finding Short Synchronizing Words for Prefix Codes
• Lower Bounds for Synchronizing Word Lengths in Partial Automata
• DFAs and PFAs with Long Shortest Synchronizing Word Length
• Modifying the upper bound on the length of minimal synchronizing word
• Using Sat solvers for synchronization issues in non-deterministic automata