Skip to content
printicon
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.

Keywords

No keywords specified

Authors

Back Edit this report
Entry responsible: Petter Ericson

Page Responsible: Frank Drewes
2022-09-30