Equational tree transformations |
| |
Authors: | Symeon Bozapalidis George Rahonis |
| |
Affiliation: | a Department of Mathematics, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greeceb Department of Foundations of Computer Science, University of Szeged, Árpád tér 2., H-6720 Szeged, Hungary |
| |
Abstract: | We define an equational relation as the union of some components of the least solution of a system of equations of tree transformations in a pair of algebras. We focus on equational tree transformations which are equational relations obtained by considering the least solutions of such systems in pairs of term algebras. We characterize equational tree transformations in terms of tree transformations defined by different bimorphisms. To demonstrate the robustness of equational tree transformations, we give equational definitions of some well-known tree transformation classes for which bimorphism characterizations also exist. These are the class of alphabetic tree transformations, the class of linear and nondeleting extended top-down tree transformations, and the class of bottom-up tree transformations and its linear and linear and nondeleting subclasses. Finally, we prove that a relation is equational if and only if it is the morphic image of an equational tree transformation. |
| |
Keywords: | Equational semantics Recognizable tree languages IO- and OI-tree substitutions Tree transformations Bimorphisms |
本文献已被 ScienceDirect 等数据库收录! |
|