Definability Results for Top-Down Tree Transducers
| Autor: | Helmut Seidl, Sebastian Maneth, Martin Vu |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Discrete mathematics
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Construct (python library) Top-down and bottom-up design Translation (geometry) Decidability Tree (data structure) Mathematics::Algebraic Geometry Transducer Computer Science::Sound Tree homomorphism Physics::Atomic and Molecular Clusters Tree transducers Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Developments in Language Theory ISBN: 9783030815073 DLT |
| DOI: | 10.1007/978-3-030-81508-0_24 |
| Popis: | We prove that for a given deterministic top-down transducer with look-ahead it is decidable whether or not its translation is definable (1) by a linear top-down tree transducer or (2) by a tree homomorphism. We present algorithms that construct equivalent such transducers if they exist. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|