Computing factorization forest of a small depth

Speaker(s)

Wojciech Tyczynski

Affiliation

Uniwersytet Warszawski

Date

Feb. 23, 2012, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Assume we have a finite set Q and set of all binary relations over Q: R_Q. Let w be the word over alphabet R_Q. An evaluation of word w is the composition of all letters of w. A factorization forest for w is a laminar family of factors of w that contains {x} for every position x. A collation of the set of consecutive factors of w is any concatenation of those factors that is also a factor of w. A set of consecutive factors is called homogeneous if all their collations have the same evaluation. A factorization forest is called homogeneous if any choice of at least three consecutive siblings is homogeneous. During the seminar I will show that for any word w we can construct a homogeneous factorization forest of height at most polynomial in |R_Q| (independently of the length of w!). I will present the algorithm for constructing such forest in time O(Q^3 w).

This algorithm is the part of Paweł Parys PhD thesis.

---