Inclusion problems for patterns with a bounded number of variables

DOI10.1016/j.ic.2012.10.003zbMath1279.68134OpenAlexW1884033210MaRDI QIDQ1932172

Dominik D. Freydenberger, Joachim Bremer

Publication date: 17 January 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.10.003

zbMATH Keywords

undecidabilitypattern languagesinclusion problemsNE-pattern languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (2)

Document spanners: from expressive power to decision problems ⋮ Pattern matching with variables: a multivariate complexity analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding a homomorphism between two words is NP-complete
• Developments from enquiries into the learnability of the pattern languages from positive data
• Bad news on decision problems for patterns
• Finding patterns common to a set of strings
• On the equivalence problem for E-pattern languages
• Frontier between decidability and undecidability: A survey
• Decision problems for patterns
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• Patterns and languages: An overview
• Extended Regular Expressions: Succinctness and Decidability
• Inclusion Problems for Patterns with a Bounded Number of Variables
• Pattern languages with and without erasing
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Four Small Universal Turing Machines

This page was built for publication: Inclusion problems for patterns with a bounded number of variables