You are not logged in | Log in

Equivalence of Deterministic Top-Down Tree Transducers is ExpTime-Complete

Speaker(s)
Adrien Boiret
Affiliation
Uniwersytet Warszawski
Date
Dec. 13, 2017, 2:15 p.m.
Room
room 5050
Seminar
Seminar Automata Theory

The class of Deterministic Top-Down Tree Transducers (DTOP) has been studied for a long time, but while its equivalence problem was known to be ExpTime-Hard, the best known algorithms were coNExpTime (search of counter-example) or 2ExpTime (full normalization).
The exact complexity bound is of relevance, as some classes that extends DTOP (lookahead, symbolic) have an equivalence problem that efficiently reduces to DTOP equivalence.
In this talk we will see an ExpTime algorithm for DTOP equivalence, derived from an algorithm that decides functionality of nondeterministic one-way word transducers.