Repetition-Free Derivability from a Regular Grammar is NP-Hard
arXiv:1602.05555
Abstract
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.
Technical report; 13 pages; 6 figures