A bottom-up automaton for tree adjoining languages
Petter Ericson · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2015
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.