Hybrid Tree Automata and the Yield Theorem for Constituent Tree Automata
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-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 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
Original language | English |
---|---|
Title of host publication | Implementation and Application of Automata |
Editors | Pascal Caron, Ludovic Mignot |
Publisher | Springer, Berlin [u. a.] |
Pages | 93-105 |
Number of pages | 13 |
ISBN (electronic) | 978-3-031-07469-1 |
ISBN (print) | 9783031074684 |
Publication status | Published - 2022 |
Peer-reviewed | Yes |
Publication series
Series | Lecture Notes in Computer Science, Volume 13266 |
---|---|
ISSN | 0302-9743 |
External IDs
Scopus | 85131956678 |
---|---|
unpaywall | 10.1007/978-3-031-07469-1_7 |