Hybrid Tree Automata and the Yield Theorem for Constituent Tree Automata

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

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 symbols can additionally be equipped with an index, i.e., a natural number which indicates the position of that symbol in the yield of the hybrid tree. As a special case of HTA, we define constituent tree automata (CTA) which recognize sets of constituent trees. We show that the set of yields of a CTA-recognizable set of constituent trees is an LCFRS language, and vice versa.

Details

OriginalspracheEnglisch
TitelImplementation and Application of Automata
Redakteure/-innenPascal Caron, Ludovic Mignot
Herausgeber (Verlag)Springer, Berlin [u. a.]
Seiten93-105
Seitenumfang13
ISBN (elektronisch)978-3-031-07469-1
ISBN (Print)9783031074684
PublikationsstatusVeröffentlicht - 2022
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Computer Science, Volume 13266
ISSN0302-9743

Externe IDs

Scopus 85131956678
unpaywall 10.1007/978-3-031-07469-1_7

Schlagworte

Bibliotheksschlagworte