arXiv Open Access 2016

Repetition-Free Derivability from a Regular Grammar is NP-Hard

Jochen Burghardt

Lihat Sumber

Abstrak

We prove the NP-hardness of the problem whether a given word can be derived from a given regular grammar without repeated occurrence of any nonterminal.

Topik & Kata Kunci

cs.FL cs.CC

Penulis (1)

Jochen Burghardt

Format Sitasi

APA MLA BibTeX

Burghardt, J. (2016). Repetition-Free Derivability from a Regular Grammar is NP-Hard. https://arxiv.org/abs/1602.05555

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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