DATE: | Wednesday, September 24th |

TIME: | 4:30 PM - 5:30 PM |

PLACE: | McConnell 320 |

TITLE: | An algorithm for enumerating all substitutions a rooted ordered tree into a term tree |

SPEAKER: | Yasuko Matsui (Tokai University) |

We consider an ordered tree with internal structured variables, called a term tree. A term tree is a rooted tree that consists of tree structures with ordered children and internal variable, and it is suited for representing tree-structured data such as HTML files. In learning theory, there are many problems on term trees. In this talk, we deal with a problem on a term tree. Let a rooted ordered tree $T$ be a term tree such that $T$ does not include internal variables.

Here we define a replacing operation is as follows:

(1)A variable of a term tree is replaced by an edge.

(2)A variable of a term tree is replaced by a subgraph of a rooted
ordered
tre e.

Now, a term tree $T_1$ and a rooted ordered tree $T_2$ are given. Then,
we consider a problem for enumerating all substitutions $T_2$ into $T_1$
where the replacing operation is permitted and an order relation of all
leaves on $T_1$ satisfies an order relation of them on $T_2$. We propose
an algorithm with polynomial delay for the above problem
using a dynamic programming technique.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at cs.mcgill.ca.

Web Address: www.cs.mcgill.ca/~beezer/Seminars/seminar99.html