SC²S Colloquium - May 11, 2016

From Sccswiki
Jump to navigation Jump to search
Date: May 11, 2016
Room: 02.07.023
Time: 3:00 pm, s.t.

Benedikt Zönnchen : Implementation of an Efficient Equivalence Test for Sequential and Linear Tree-to-Word Transducers

Transducers are applied to various areas in computer science. Especially, tree- to-word transducers are of great interest, since they allow concatenation in the output and they are a suitable model for general XML transformations. We study the equivalence problem for sequential and linear tree-to-word transducers and present a polynomial time algorithm. The algorithm consists of a chain of polynomial time reductions, which ends with the reduction to the morphism equivalence problem on context-free language, which is in Ptime. We discuss the theoretical background, give complexities for all involved algorithms and explain certain algorithms in detail. In our setting, the output is represented by straight-line programs i. e. the output is compressed. Therefore, we implemented a set of algorithms to work with large words especially to test equality of slp-compressed words.