Bad News on Decision Problems for Patterns

DOI10.1007/978-3-540-85780-8_26MaRDI QIDQ3533022zbMATH OpenOpenAlexFDO

Authors Dominik D. Freydenberger, Daniel Reidenbach

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://dspace.lboro.ac.uk/2134/5593

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Bad news on decision problems for patterns
• Decision problems for patterns
• New problems of pattern avoidance
• Open Problems in Pattern Avoidance
• Publication:4942653
• On some decision problems in programming
• On the complexity of finding emerging patterns
• scientific article; zbMATH DE number 522839

Cites work

• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• A non-learnable class of E-pattern languages
• A note on the equivalence problem of \(E\)-patterns
• An examination of Ohlebusch and Ukkonen's conjecture on the equivalence problem for E-pattern languages
• Decision problems for patterns
• Developments from enquiries into the learnability of the pattern languages from positive data
• Discontinuities in pattern inference
• Finding patterns common to a set of strings
• Finite degrees of ambiguity in pattern languages
• scientific article; zbMATH DE number 996382 (Why is no real title available?)
• scientific article; zbMATH DE number 4051031 (Why is no real title available?)
• scientific article; zbMATH DE number 2150289 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3806956 (Why is no real title available?)
• Inductive inference of formal languages from positive data
• Learning Theory
• On the equivalence problem for E-pattern languages
• Pattern languages with and without erasing
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The expressibility of languages and relations by word equations
• UNAMBIGUOUS MORPHIC IMAGES OF STRINGS

Cited in

(10)

• On the language equivalence of NE star-patterns
• Bad news on decision problems for patterns
• A note on the equivalence problem of \(E\)-patterns
• Decision problems for patterns
• Inclusion problems for patterns with a bounded number of variables
• On the decidability of infix inclusion problem
• Inclusion problems for patterns with a bounded number of variables
• Existence and Nonexistence of Descriptive Patterns
• Inclusion is undecidable for pattern languages
• On the decidability of infix inclusion problem

This page was built for publication: Bad News on Decision Problems for Patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533022)