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.