Bad News on Decision Problems for Patterns

DOI10.1007/978-3-540-85780-8_26zbMath1161.68526OpenAlexW3021575622MaRDI QIDQ3533022

Daniel Reidenbach, Dominik D. Freydenberger

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)

Related Items (2)

Existence and Nonexistence of Descriptive Patterns ⋮ Bad news on decision problems for patterns

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• A non-learnable class of E-pattern languages
• 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
• A note on the equivalence problem of \(E\)-patterns
• On the equivalence problem for E-pattern languages
• Decision problems for patterns
• Inductive inference of formal languages from positive data
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Finite degrees of ambiguity in pattern languages
• The expressibility of languages and relations by word equations
• Pattern languages with and without erasing
• Learning Theory
• UNAMBIGUOUS MORPHIC IMAGES OF STRINGS
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS

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