6533b839fe1ef96bd12a632f
RESEARCH PRODUCT
Pattern languages with and without erasing
Tao JiangKai SalomaaEfim KinberArto SalomaaSheng Yusubject
business.industryApplied MathematicsInferenceComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Inductive reasoningcomputer.software_genreComputer Science ApplicationsPhilosophy of languageComputational Theory and MathematicsrestrictFormal languageArtificial intelligenceEquivalence (formal languages)ArithmeticbusinesscomputerComputer Science::Formal Languages and Automata TheoryNatural language processingMathematicsdescription
The paper deals with the problems related to finding a pattern common to all words in a given set. We restrict our attention to patterns expressible by the use of variables ranging over words. Two essentially different cases result, depending on whether or not the empty word belongs to the range. We investigate equivalence and inclusion problems, patterns descriptive for a set, as well as some complexity issues. The inclusion problem between two pattern languages turns out to be of fundamental theoretical importance because many problems in the classical combinatorics of words can be reduced to it.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1994-01-01 | International Journal of Computer Mathematics |