Synthesis of deterministic top-down tree transducers from automatic tree relations

DOI10.1016/J.IC.2016.07.013MaRDI QIDQ515670zbMATHOpenAlexFDO

Authors Christof Löding, Sarah Winter

Publication date 16 March 2017

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

decidabilityuniformizationtree automatontree transducerautomatic relation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Abstract: We consider the synthesis of deterministic tree transducers from automaton definable specifications, given as binary relations, over finite trees. We consider the case of specifications that are deterministic top-down tree automatic, meaning the specification is recognizable by a deterministic top-down tree automaton that reads the two given trees synchronously in parallel. In this setting we study tree transducers that are allowed to have either bounded delay or arbitrary delay. Delay is caused whenever the transducer reads a symbol from the input tree but does not produce output. We provide decision procedures for both bounded and arbitrary delay that yield deterministic top-down tree transducers which realize the specification for valid input trees. Similar to the case of relations over words, we use two-player games to obtain our results.

Recommendations

• Synthesis of deterministic top-down tree transducers from automatic tree relations
• Deterministic bottom-up tree transducers and ground term rewrite systems
• Top-down tree transducers with deterministic top-down look-ahead
• Deterministic top-down tree transducers with iterated look-ahead
• Definability results for top-down tree transducers
• Definability Results for Top-Down Tree Transducers
• Uniformization problems for tree-automatic relations and top-down tree transducers
• On injectivity of deterministic top-down tree transducers
• scientific article; zbMATH DE number 3858450
• Superlinear deterministic top-down tree transducers

Cites work

• scientific article; zbMATH DE number 3492660 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 6741931 (Why is no real title available?)
• scientific article; zbMATH DE number 3328724 (Why is no real title available?)
• scientific article; zbMATH DE number 3189696 (Why is no real title available?)
• Automata, logics, and infinite games. A guide to current research
• Degrees of lookahead in regular infinite games
• On tree transducers for partial functions
• Solving Sequential Conditions by Finite-State Strategies
• Synthesis of deterministic top-down tree transducers from automatic tree relations
• Typechecking for XML transformers

Cited in

(9)

• Deterministic bottom-up tree transducers and ground term rewrite systems
• The complexity of transducer synthesis from multi-sequential specifications
• Logics for word transductions with synthesis
• Definability Results for Top-Down Tree Transducers
• How much lookahead is needed to win infinite games?
• Superlinear deterministic top-down tree transducers
• How Much Lookahead is Needed to Win Infinite Games?
• Uniformization problems for tree-automatic relations and top-down tree transducers
• Synthesis of deterministic top-down tree transducers from automatic tree relations

This page was built for publication: Synthesis of deterministic top-down tree transducers from automatic tree relations

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