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 cs.mcgill.ca.