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.