Pattern languages with and without erasing

DOI10.1080/00207169408804252zbMath0939.68690OpenAlexW2035166717MaRDI QIDQ4839719

Tao Jiang, Kai Salomaa, Arto Salomaa, E. B. Kinber, Sheng Yu

Publication date: 4 July 2000

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169408804252

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A parameterized study of maximum generalized pattern matching problems, Remarks on arbitrary multiple pattern interpretations, On the parameterised complexity of string morphism problems, A note on the equivalence problem of \(E\)-patterns, Document spanners: from expressive power to decision problems, Closure properties of pattern languages, Inferring descriptive generalisations of formal languages, Regular and context-free pattern languages over small alphabets, On the equivalence problem for E-pattern languages, Inclusion problems for patterns with a bounded number of variables, Bad News on Decision Problems for Patterns, Discontinuities in pattern inference, Inclusion is undecidable for pattern languages, Finite degrees of ambiguity in pattern languages, Pattern systems, Multi-pattern languages, Restricted ambiguity of erasing morphisms, Existence and nonexistence of descriptive patterns, Finitely distinguishable erasing pattern languages, A Polynomial Time Match Test for Large Classes of Extended Regular Expressions, Existence and Nonexistence of Descriptive Patterns, 2-testability and relabelings produce everything, Bad news on decision problems for patterns, Pattern matching with variables: a multivariate complexity analysis, A non-learnable class of E-pattern languages

Cites Work

• Finding patterns common to a set of strings
• Learning regular languages from counterexamples
• Inductive inference of formal languages from positive data