McGill University - School of Computer Science

Algorithms Seminar 2003

Everybody is welcome!

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 
Web Address: