Deciding the Twins Property for Weighted Tree Automata over Extremal Semifields
Matthias Büchse, Anja Fischer · 2012
It has remained an open question whether the twins property for weighted tree automata is decidable. This property is crucial for determinizing such an automaton, and it has been argued that determinization improves the output of parsers and translation systems. We show that the twins property for weighted tree automata over extremal semifields is decidable. 1