×

zbMATH — the first resource for mathematics

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.

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI