Containment Problems for Pattern Languages
Summary :
A pattern is a finite string of constant symbols and variable symbols. The language of a pattern is the set of all strings obtained by substituting any nonnull constant string for each variable symbol in the pattern. The class of pattern languages was introduced by Angluin in 1979 as a concrete class which is inferable from positive data. In this paper, we consider the decision problem whether for given two patterns there is a containment relation between their languages, which was posed by Angluin and its decidability remains open. We give some sufficient conditions to make this problem decidable. We also introduce the notions of generalizations and minimal generalizations common to a set of patterns. We characterize the above open problem using the minimal generalization.
- Publication
- IEICE TRANSACTIONS on Information Vol.E75-D No.4 pp.420-425
- Publication Date
- 1992/07/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Algorithmic Learning Theory)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yasuhito MUKOUCHI, "Containment Problems for Pattern Languages" in IEICE TRANSACTIONS on Information,
vol. E75-D, no. 4, pp. 420-425, July 1992, doi: .
Abstract: A pattern is a finite string of constant symbols and variable symbols. The language of a pattern is the set of all strings obtained by substituting any nonnull constant string for each variable symbol in the pattern. The class of pattern languages was introduced by Angluin in 1979 as a concrete class which is inferable from positive data. In this paper, we consider the decision problem whether for given two patterns there is a containment relation between their languages, which was posed by Angluin and its decidability remains open. We give some sufficient conditions to make this problem decidable. We also introduce the notions of generalizations and minimal generalizations common to a set of patterns. We characterize the above open problem using the minimal generalization.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_4_420/_p
Copy
@ARTICLE{e75-d_4_420,
author={Yasuhito MUKOUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Containment Problems for Pattern Languages},
year={1992},
volume={E75-D},
number={4},
pages={420-425},
abstract={A pattern is a finite string of constant symbols and variable symbols. The language of a pattern is the set of all strings obtained by substituting any nonnull constant string for each variable symbol in the pattern. The class of pattern languages was introduced by Angluin in 1979 as a concrete class which is inferable from positive data. In this paper, we consider the decision problem whether for given two patterns there is a containment relation between their languages, which was posed by Angluin and its decidability remains open. We give some sufficient conditions to make this problem decidable. We also introduce the notions of generalizations and minimal generalizations common to a set of patterns. We characterize the above open problem using the minimal generalization.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Containment Problems for Pattern Languages
T2 - IEICE TRANSACTIONS on Information
SP - 420
EP - 425
AU - Yasuhito MUKOUCHI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - July 1992
AB - A pattern is a finite string of constant symbols and variable symbols. The language of a pattern is the set of all strings obtained by substituting any nonnull constant string for each variable symbol in the pattern. The class of pattern languages was introduced by Angluin in 1979 as a concrete class which is inferable from positive data. In this paper, we consider the decision problem whether for given two patterns there is a containment relation between their languages, which was posed by Angluin and its decidability remains open. We give some sufficient conditions to make this problem decidable. We also introduce the notions of generalizations and minimal generalizations common to a set of patterns. We characterize the above open problem using the minimal generalization.
ER -
English
