Restricted ground tree transducers

DOI10.1016/S0304-3975(99)00135-8MaRDI QIDQ1589437zbMATH OpenFDO

Authors Zoltán Fülöp, Sándor Vágvölgyi

Publication date 12 December 2000

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

Full work available at URL https://doi.org/10.1016/S0304-3975(99)00135-8

zbMATH Keywords

ground term rewriting systemsground tree transducerstree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

We consider restricted versions of ground tree transducers: total, deterministic, and symmetric subclasses and all other subclasses created by applying any combination of these restrictions. We present the inclusion diagram of the tree transformation classes induced by these restricted ground tree transducers. We show that the following four classes of term relations are the same: (i) tree transformations induced by symmetric deterministic ground tree transducers, (ii) congruence relations on term algebras induced by reduced ground term rewriting systems, (iii) congruence relations on term algebras induced by convergent ground term rewriting systems, and (iv) finitely generated congruence relations on term algebras. As a by-product of our results, we obtain a new ground completion algorithm. Moreover, we show that the following three classes of term relations on term algebras with at least one non-nullary function symbol are also the same: (i) tree transformations induced by total symmetric deterministic ground tree transducers, (ii) congruence relations on term algebras of finite index, (iii) finitely generated congruence relations on term algebras of which the trunk is the whole set of terms.

Recommendations

• Deterministic bottom-up tree transducers and ground term rewrite systems
• On ground tree transformations and congruences induced by tree automata.
• A complete classification of deterministic root-to-frontier tree transformation classes
• Term rewriting restricted to ground terms.
• Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations

Cites work

• 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
• A Note on the Congruence Lattice of a Finitely Generated Algebra
• 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.
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 4135419 (Why is no real title available?)
• scientific article; zbMATH DE number 1192316 (Why is no real title available?)
• scientific article; zbMATH DE number 58292 (Why is no real title available?)
• scientific article; zbMATH DE number 1337744 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• Minimal equational representations of recognizable tree languages
• Proof lengths for equational completion
• Shostak's congruence closure as completion
• The Church-Rosser property for ground term-rewriting systems is decidable
• Tree generating regular systems

Cited in

(4)

• Intersection of finitely generated congruences over term algebra
• Term rewriting restricted to ground terms.
• On ground tree transformations and congruences induced by tree automata.
• Symbol different term rewrite systems

This page was built for publication: Restricted ground tree transducers

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