First-order tree-to-tree functions

DOI10.1145/3373718.3394785MaRDI QIDQ5145635zbMATH OpenOpenAlexFDO

Authors Mikołaj Bojańczyk, Amina Doumane

Publication date 21 January 2021

Published in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.09307

zbMATH Keywords

automatafirst-order logicmonadic second-order logictree transducer

Mathematics Subject Classification ID

Classical first-order logic (03B10) Higher-order logic (03B16) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Abstract: We study tree-to-tree transformations that can be defined in first-order logic or monadic second-order logic. We prove a decomposition theorem, which shows that every transformation can be obtained from prime transformations, such as tree-to-tree homomorphisms or pre-order traversal, by using combinators such as function composition.

Recommendations

• scientific article; zbMATH DE number 475423
• A complete classification of deterministic root-to-frontier tree transformation classes
• Compositions of tree series transformations
• Publication:3028362
• Sur une classe de transformations d'arbres

Cited in

(5)

• Tree-Width for First Order Formulae
• Implicit automata in -calculi. III: Affine planar string-to-string functions
• Deciding linear height and linear size-to-height increase of macro tree transducers
• Comparison-free polyregular functions
• Learning tree pattern transformations

This page was built for publication: First-order tree-to-tree functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145635)