Inclusion problems for patterns with a bounded number of variables

DOI10.1007/978-3-642-14455-4_11MaRDI QIDQ3584885zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

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
• Extended regular expressions: succinctness and decidability
• A note on the complexity of matching patterns with variables

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)