Skip to content
Show report in:

UMINF 15.14

A Bottom-up Automaton for Tree-Adjoining Languages

Current tree parsing algorithms for nonregular tree languages all have superlinear running times, possibly limiting their practical applicability. We present a bottom-up tree automaton that captures exactly the tree-adjoining languages in the non-deterministic case. The determinstic case captures a strict superset of the regular tree languages, while preserving running times linear in the size of the tree.


No keywords specified


Back Edit this report
Entry responsible: Petter Ericson

Page Responsible: Frank Drewes