Hybrid tree automata and the yield theorem for constituent tree automata.

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

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.

Details

Original languageEnglish
Article number114185
JournalTheoretical computer science : the journal of the EATCS
Volume979
Publication statusPublished - 10 Nov 2023
Peer-reviewedYes

External IDs

Scopus 85173478895

Keywords