Alphabetic tree relations
type: Item
instance of: scholarly article
title: Alphabetic tree relations
zbMATH Open document ID: 0765.68068
DOI: 10.1016/0304-3975(92)90348-J
author: Symeon Bozapalidis
published in: Theoretical Computer Science
publication date: 1992-09-27T00:00:00Z
review text: The alphabetic tree relations studied in this paper are tree transformations defined by bimorphisms (\(\varphi,R,\psi)\) in which \(\varphi\) and \(\psi\) are alphabetic tree homomorphisms and \(R\) is a recognizable tree language. The class Aleph of these tree relations is shown to contain the inverses and the compositions of its members. These transformations also preserve recognizable and algebraic tree languages. Several natural types of tree transformations are shown to be in Aleph and the class is compared with some other classes of tree transformations. A key notion in the paper is a certain join operation for combining ranked alphabets.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 65329
zbMATH Keywords: tree transformations
zbMATH Keywords: bimorphisms
zbMATH Keywords: tree languages
MaRDI profile type: Publication
cites work: Forêts Algébriques et Homomorphismes Inverses
cites work: Tree transducers and tree languages
cites work: Q3859267
cites work: Sur une classe de transformations d'arbres
cites work: Actions, finite state sets and applications to trees
cites work: A representation of trees by languages. II
cites work: Q4160428
cites work: Q4079524
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: Q4167602
cites work: IO and OI. I
cites work: Mappings and grammars on trees
cites work: Q4766920
cites work: Generalized sequential machine maps
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
description: scientific article; zbMATH DE number 65329