Patterns with bounded treewidth

DOI10.1016/j.ic.2014.08.010zbMath1309.68123OpenAlexW4205732092MaRDI QIDQ476169

Markus L. Schmid, Daniel Reidenbach

Publication date: 28 November 2014

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

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

zbMATH Keywords

treewidthmembership problempattern languagesextended regular expressionsparameterised pattern matching

Mathematics Subject Classification ID

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

Related Items

Blocksequences of \(k\)-local words, A parameterized study of maximum generalized pattern matching problems, Revisiting Shinohara's algorithm for computing descriptive patterns, Document spanners: from expressive power to decision problems, Closure properties of pattern languages, Distinguishing pattern languages with membership examples, Matching patterns with variables under edit distance, On the Complexity of Solving Restricted Word Equations, Unnamed Item, On the Solvability Problem for Restricted Classes of Word Equations, Unnamed Item, A logic for document spanners, The hardness of solving simple word equations, Pattern matching with variables: a multivariate complexity analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time inference of arbitrary pattern languages
• 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 partial k-arboretum of graphs with bounded treewidth
• An average-case optimal one-variable pattern language learner
• Parameterized pattern matching: Algorithms and applications
• Generalized function matching
• Parametrized complexity theory.
• Patterns with Bounded Treewidth
• Finding Shuffle Words That Represent Optimal Scheduling of Shared Memory Access
• A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
• Learning Relational Patterns
• Inclusion Problems for Patterns with a Bounded Number of Variables
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Stochastic finite learning of the pattern languages