| 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.