Inclusion problems for patterns with a bounded number of variables

DOI10.1007/978-3-642-14455-4_11zbMATH Open1250.68148OpenAlexW4256185386MaRDI QIDQ3584885FDOQ3584885

Authors: Joachim Bremer, Dominik D. Freydenberger 

Publication date: 31 August 2010

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

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

Recommendations

• Inclusion problems for patterns with a bounded number of variables
• Inclusion is undecidable for pattern languages
• Decision problems for patterns
• Bad News on Decision Problems for Patterns
• Bad news on decision problems for patterns

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (6)

• Patterns with bounded treewidth
• Inclusion problems for patterns with a bounded number of variables
• Regular and context-free pattern languages over small alphabets
• Inclusion is undecidable for pattern languages
• A note on the complexity of matching patterns with variables
• Extended regular expressions: succinctness and decidability

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

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