Hybrid Tree Automata and the Yield Theorem for Constituent Tree Automata

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-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 languageEnglish
Title of host publicationImplementation and Application of Automata
EditorsPascal Caron, Ludovic Mignot
PublisherSpringer, Berlin [u. a.]
Pages93-105
Number of pages13
ISBN (electronic)978-3-031-07469-1
ISBN (print)9783031074684
Publication statusPublished - 2022
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science, Volume 13266
ISSN0302-9743

External IDs

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

Keywords

Library keywords