Decision problems for patterns. (English) Zbl 0827.68066

Summary: We settle an open problem, the inclusion problem for pattern languages. This is the first known case where inclusion is undecidable for generative devices having a trivially decidable equivalence problem. The study of patterns goes back to the seminal work of Thue and is important also, for instance, in recent work concerning inductive inference and learning. Our results concern both erasing and non-erasing patterns.


68Q45 Formal languages and automata
Full Text: DOI Link