✦ LIBER ✦

Bad news on decision problems for patterns

✍ Scribed by Dominik D. Freydenberger; Daniel Reidenbach

Book ID: 113641854
Publisher: Elsevier Science
Year: 2010
Tongue: English
Weight: 248 KB
Volume: 208
Category: Article
ISSN: 0890-5401
DOI: 10.1016/j.ic.2009.04.002

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Decision Problems for Patterns

✍ T. Jiang; A. Salomaa; K. Salomaa; S. Yu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 742 KB

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

On decision problems for parameterized m

On decision problems for parameterized machines

✍ Oscar H. Ibarra; Igor Potapov; Hsu-Chun Yen 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 580 KB

On two-dimensional pattern-matching lang

On two-dimensional pattern-matching languages and their decision problems

✍ Kenichi Morita; Kaoru Nakazono; Kazuhiro Sugata 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 678 KB

On incentive design for dynamic decision

On incentive design for dynamic decision problems

✍ Harri Ehtamo; Raimo P. Hämäläinen 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 135 KB

On undecidability bounds for matrix deci

On undecidability bounds for matrix decision problems

✍ Paul Bell; Igor Potapov 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 313 KB

On some decision problems for RAM progra

On some decision problems for RAM programs

✍ Oscar H. Ibarra; Shlomo Moran 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 706 KB