We introduce an automaton model for recognizing sets of hybrid trees, the hybrid tree automaton (HTA). Special cases of hybrid trees are constituent trees and dependency trees, as they occur in natural language processing. This includes the cases of discontinuous constituent trees and non-projective dependency trees. In general, a hybrid tree is a tree over a ranked alphabet in which a symbol can additionally be equipped with a natural number, called index; in a hybrid tree, each index occurs at most once. The yield of a hybrid tree is a sequence of strings over those symbols which occur in an indexed form; the corresponding indices determine the order within these strings; the borders between two consecutive strings are determined by the gaps in the sequence of indices. As a special case of HTA, we define constituent tree automata (CTA) which recognize sets of constituent trees. We introduce the notion of CTA-inductively recognizable and we show that the set of yields of a CTA-inductively recognizable set of constituent trees is an LCFRS language, and vice versa.

We present the first supertagging-based parser for linear context-free rewriting systems (LCFRS).It utilizes neural classifiers and outperforms previous LCFRS-based parsers in both accuracy and parsing speed by a wide margin.Our results keep up with the best (general) discontinuous parsers, particularly the scores for discontinuous constituents establish a new state of the art.The heart of our approach is an efficient lexicalization procedure which induces a lexical LCFRS from any discontinuous treebank.We describe a modification to usual chart-based LCFRS parsing that accounts for supertagging and introduce a procedure that transforms lexical LCFRS derivations into equivalent parse trees of the original treebank.Our approach is evaluated on the English Discontinuous Penn Treebank and the German treebanks Negra and Tiger.A hearing is scheduled on the issue today VP VP NP NP DT NN PP IN NP DT NN VBN NP NN VBZ NP 2 → (x 1 , y 1 ) (NP, PP) NP → (x 1 y 1 ) (DT, NN) DT → (A) NN → (hearing) PP → (x 1 y 1 ) (IN, NP) IN → (on) NP → (x 1 y 1 ) (DT, NN) DT → (the) NN → (issue)