Pattern languages with and without erasing

DOI10.1080/00207169408804252MaRDI QIDQ4839719zbMATH OpenOpenAlexFDO

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

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

Cited in

(28)

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

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)