Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
The Power of Regularity-Preserving Multi Bottom-up Tree Transducers
verfasst von : Andreas Maletti
Erschienen in: Implementation and Application of Automata
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The expressive power of regularity-preserving multi bottom-up tree transducers (
mbot
) is investigated. These
mbot
have very attractive theoretical and algorithmic properties. However, their expressive power is not well understood. It is proved that despite the restriction their power still exceeds that of composition chains of linear extended top-down tree transducers with regular look-ahead (
xtop
R
), which are a natural super-class of
stsg
. In particular, topicalization can be modeled by such
mbot
, whereas composition chains of
xtop
R
cannot implement it. However, the inverse of topicalization cannot be implemented by any
mbot
. An interesting, promising, and widely applicable proof technique is used to prove those statements.