IEICE TRANSACTIONS on Information
Polynomial Time Inference of Unions of Two Tree Pattern Languages
Summary :
In this paper, we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm, we can realize a consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.
- Publication
- IEICE TRANSACTIONS on Information Vol.E75-D No.4 pp.426-434
- 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
Hiroki ARIMURA, Takeshi SHINOHARA, Setsuko OTSUKI, "Polynomial Time Inference of Unions of Two Tree Pattern Languages" in IEICE TRANSACTIONS on Information,
vol. E75-D, no. 4, pp. 426-434, July 1992, doi: .
Abstract: In this paper, we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm, we can realize a consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_4_426/_p
Copy
@ARTICLE{e75-d_4_426,
author={Hiroki ARIMURA, Takeshi SHINOHARA, Setsuko OTSUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial Time Inference of Unions of Two Tree Pattern Languages},
year={1992},
volume={E75-D},
number={4},
pages={426-434},
abstract={In this paper, we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm, we can realize a consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Polynomial Time Inference of Unions of Two Tree Pattern Languages
T2 - IEICE TRANSACTIONS on Information
SP - 426
EP - 434
AU - Hiroki ARIMURA
AU - Takeshi SHINOHARA
AU - Setsuko OTSUKI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - July 1992
AB - In this paper, we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm, we can realize a consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.
ER -
English
