On ground tree transformations and congruences induced by tree automata.

DOI10.1016/S0304-3975(03)00279-2MaRDI QIDQ1401416zbMATH OpenOpenAlexFDO

Authors Sándor Vágvölgyi

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(03)00279-2

zbMATH Keywords

Tree automataGround term rewrite systemsGround tree transducers

Mathematics Subject Classification ID

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

Recommendations

• Recognizing relations by tree automata
• Deterministic bottom-up tree transducers and ground term rewrite systems
• Restricted ground tree transducers
• Congruences, homomorphisms and languages of tree automata
• A fast algorithm for constructing a tree automaton recognizing a congruential tree language

Cites work

• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 58292 (Why is no real title available?)
• scientific article; zbMATH DE number 749931 (Why is no real title available?)
• A fast algorithm for constructing a tree automaton recognizing a congruential tree language
• A fast algorithm for generating reduced ground rewriting systems from a set of ground equations
• Congruential complements of ground term rewrite systems
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Derivation trees of ground term rewriting systems.
• Minimal equational representations of recognizable tree languages
• Proof lengths for equational completion
• Restricted ground tree transducers
• Shostak's congruence closure as completion
• The Church-Rosser property for ground term-rewriting systems is decidable
• Tree generating regular systems

Cited in

(7)

• Restricted ground tree transducers
• Recognizing relations by tree automata
• A fast algorithm for constructing a tree automaton recognizing a congruential tree language
• Congruences, homomorphisms and languages of tree automata
• scientific article; zbMATH DE number 7315101 (Why is no real title available?)
• Approximate consistency for transformations on words and trees
• The ground tree transducer game with identical tree automata

This page was built for publication: On ground tree transformations and congruences induced by tree automata.

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