Bad news on decision problems for patterns
From MaRDI portal
Publication:1049406
DOI10.1016/j.ic.2009.04.002zbMath1189.68071OpenAlexW2111415409MaRDI QIDQ1049406
Daniel Reidenbach, Dominik D. Freydenberger
Publication date: 12 January 2010
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://dspace.lboro.ac.uk/2134/5593
Related Items (13)
Revisiting Shinohara's algorithm for computing descriptive patterns ⋮ Document spanners: from expressive power to decision problems ⋮ Closure properties of pattern languages ⋮ Inferring descriptive generalisations of formal languages ⋮ Distinguishing pattern languages with membership examples ⋮ Regular patterns, regular languages and context-free languages ⋮ Regular and context-free pattern languages over small alphabets ⋮ Inclusion problems for patterns with a bounded number of variables ⋮ On the undecidability and descriptional complexity of synchronized regular expressions ⋮ A note on the complexity of matching patterns with variables ⋮ Existence and nonexistence of descriptive patterns ⋮ Finitely distinguishable erasing pattern languages ⋮ Pattern matching with variables: a multivariate complexity analysis
Cites Work
- 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
- Bad News on 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
