arXiv Open Access 2009

Approximating the minimum length of synchronizing words is hard

M. V. Berlinkov

Lihat Sumber

Abstrak

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

Topik & Kata Kunci

cs.FL cs.CC

Penulis (1)

M. V. Berlinkov

Format Sitasi

APA MLA BibTeX

Berlinkov, M.V. (2009). Approximating the minimum length of synchronizing words is hard. https://arxiv.org/abs/0909.3787

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2009
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓