Loading…
Bad news on decision problems for patterns
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 languag...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Default Article |
| Published: |
2010
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/2134/5593 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823271280261988352 |
|---|---|
| author | Dominik Freydenberger Daniel Reidenbach |
| author_facet | Dominik Freydenberger Daniel Reidenbach |
| author_sort | Dominik Freydenberger (3718891) |
| collection | Figshare |
| description | 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. |
| format | Default Article |
| id | rr-article-9402878 |
| institution | Loughborough University |
| publishDate | 2010 |
| record_format | Figshare |
| spelling | rr-article-94028782010-01-01T00:00:00Z Bad news on decision problems for patterns Dominik Freydenberger (3718891) Daniel Reidenbach (1256598) Other information and computing sciences not elsewhere classified untagged Information and Computing Sciences not elsewhere classified 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. 2010-01-01T00:00:00Z Text Journal contribution 2134/5593 https://figshare.com/articles/journal_contribution/Bad_news_on_decision_problems_for_patterns/9402878 CC BY-NC-ND 4.0 |
| spellingShingle | Other information and computing sciences not elsewhere classified untagged Information and Computing Sciences not elsewhere classified Dominik Freydenberger Daniel Reidenbach Bad news on decision problems for patterns |
| title | Bad news on decision problems for patterns |
| title_full | Bad news on decision problems for patterns |
| title_fullStr | Bad news on decision problems for patterns |
| title_full_unstemmed | Bad news on decision problems for patterns |
| title_short | Bad news on decision problems for patterns |
| title_sort | bad news on decision problems for patterns |
| topic | Other information and computing sciences not elsewhere classified untagged Information and Computing Sciences not elsewhere classified |
| url | https://hdl.handle.net/2134/5593 |