Hybrid Tree Automata and the Yield Theorem for Constituent Tree Automata
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
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
Originalsprache | Englisch |
---|---|
Titel | Implementation and Application of Automata |
Redakteure/-innen | Pascal Caron, Ludovic Mignot |
Herausgeber (Verlag) | Springer, Cham |
Seiten | 93-105 |
Seitenumfang | 13 |
ISBN (elektronisch) | 978-3-031-07469-1 |
ISBN (Print) | 9783031074684 |
Publikationsstatus | Veröffentlicht - 2022 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | Lecture Notes in Computer Science |
---|---|
Band | 13266 |
ISSN | 0302-9743 |
Externe IDs
Scopus | 85131956678 |
---|---|
unpaywall | 10.1007/978-3-031-07469-1_7 |