We study the inclusion problem for pattern languages, which - due to Jiang
et al. (Journal of Computer and System Sciences 50, 1995) - is known to be
undecidable. More precisely, Jiang et al. demonstrate that there is no effective
procedure deciding the inclusion for the class of all pattern languages over all
alphabets. Most applications of pattern languages, however, consider classes
over fixed alphabets, and therefore it is practically more relevant to ask for the
existence of alphabet-specific decision procedures. Our first main result states
that, for all but very particular cases, this version of the inclusion problem is also
undecidable. The second main part of our paper disproves the prevalent conjecture
on the inclusion of so-called similar E-pattern languages, and it explains
the devastating consequences of this result for the intensive previous research
on the most prominent open decision problem for pattern languages, namely
the equivalence problem for general E-pattern languages.
History
School
Science
Department
Computer Science
Citation
FREYDENBERGER, D.D. and REIDENBACH, D., 2010. Bad news on decision problems for patterns. Information and Computation, 208 (1), pp. 83-96.