Pattern languages with and without erasing

DOI10.1080/00207169408804252zbMATH Open0939.68690OpenAlexW2035166717MaRDI QIDQ4839719FDOQ4839719

Authors: Tao Jiang, Kai Salomaa, Efim Kinber, Arto Salomaa, 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)

Cites Work

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

Cited In (26)

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

This page was built for publication: Pattern languages with and without erasing

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