Equational weighted tree transformations
type: Item
instance of: scholarly article
title: Equational weighted tree transformations
zbMATH Open document ID: 1244.68054
author: Symeon Bozapalidis
author: Zoltán Fülöp
author: George Rahonis
published in: Acta Informatica
publication date: 2012-03-23T00:00:00Z
review text: The authors consider polynomial systems of equations of weighted term relations over commutative continuous semirings. A weighted relation between two algebras is called equational if it is a component of the least solution of such a system. This least solution is obtained as the least fixed point of an \(\omega\)-continuous operator. Equational weighted tree transformations are the equational weighted relations between two term algebras. The equational weighted tree transformations, as well as some special types of them, are characterized in terms of weighted tree bimorphisms, i.e., systems consisting of two tree homomorphisms and a recognizable weighted tree language. Furthermore, the weighted tree transformations computed by weighted linear nondeleting tree transducers and weighted linear nondeleting extended tree transducers are given equational characterizations. Finally, the authors present a Mezei-Wright like result showing that the weighted equational relations between any two algebras are the images of a certain kind of weighted equational tree transformations.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 6018102
zbMATH Keywords: weighted tree transformations
zbMATH Keywords: weighted equational sets
zbMATH Keywords: tree bimorphisms
zbMATH Keywords: tree transducers
zbMATH Keywords: tree languages
zbMATH Keywords: Mezei-Wright theorems
MaRDI profile type: Publication
full work available at URL: s00236-011-0148-5
OpenAlex ID: W1990698263
cites work: Weighted grammars and Kleene's theorem
cites work: Q4138171
cites work: Morphismes et bimorphismes d'arbres
cites work: Recognizable formal power series on trees
cites work: Effective construction of the syntactic algebra of a recognizable series on trees
cites work: Représentations matricielles des séries d'arbre reconnaissables
cites work: Equational elements in additive algebras
cites work: Equational tree transformations
cites work: Q3431477
cites work: Q5639639
cites work: Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
cites work: Basic notions of universal algebra for language theory and graph grammars
cites work: Weighted finite automata over strong bimonoids
cites work: Q4079524
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: IO and OI. I
cites work: IO and OI. II
cites work: Q3150247
cites work: Q4449537
cites work: Fuzzy tree automata
cites work: Q4654640
cites work: General varieties of tree languages
cites work: Q4700998
cites work: Q4269222
cites work: RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA
cites work: Compositions of tree series transformations
cites work: Compositions of extended top-down tree transducers
cites work: Survey: Weighted extended top-down tree transducers. I. Basics and expressive power
cites work: Q3735051
cites work: Algebraic automata and context-free sets
cites work: Q4002149
DOI: 10.1007/S00236-011-0148-5
description: scientific article; zbMATH DE number 6018102