We settle an open problem, the inclusion problem for pattern languages
. This is the first known case where inclusion is undecidable for gene
rative devices having a trivially decidable equivalence problem. The s
tudy of patterns goes back to the seminal work of Thue and is importan
t also, for instance, in recent work concerning inductive inference an
d learning. Our results concern both erasing and nonerasing patterns.
(C) 1995 Academic Press, Inc.