The search functionality is under construction.

Keyword Search Result

[Keyword] inference from positive data(1hit)

1-1hit
  • Polynomial Time Inference of Unions of Two Tree Pattern Languages

    Hiroki ARIMURA  Takeshi SHINOHARA  Setsuko OTSUKI  

     
    PAPER

      Vol:
    E75-D No:4
      Page(s):
    426-434

    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.