Paper Info
Title
Bad news on decision problems for patterns
Abstract
We study the inclusion problem for pattern languages, which-due to Jiang et al. [T. Jiang, A. Salomaa, K. Salomaa, S. Yu, Decision problems for patterns, Journal of Computer and System Sciences 50 (1995) 53-63]-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.
Year
DOI
Venue
2010
10.1016/j.ic.2009.04.002
Information & Computation
Keywords
Field
DocType
pattern language,general e-pattern language,alphabet-specific decision procedure,decision problem,t. jiang,equivalence problem,k. salomaa,prominent open decision problem,bad news,inclusion problem,main part
Discrete mathematics,Inductive reasoning,Mathematical economics,Decision problem,Computer science,Abstract family of languages,Pattern language,Equivalence (measure theory),Artificial intelligence,Conjecture,Undecidable problem,Alphabet
Journal
Volume
Issue
ISSN
208
1
Information and Computation
Citations 
PageRank 
References 
14
0.68
19
Authors
2
Name
Order
Citations
PageRank
Dominik D. Freydenberger1899.14
Daniel Reidenbach215418.06