On two families of forests
type: Item
instance of: scholarly article
title: On two families of forests
zbMATH Open document ID: 0790.68055
DOI: 10.1007/BF01218405
author: Symeon Bozapalidis
author: George Rahonis
published in: Acta Informatica
publication date: 1994-06-02T00:00:00Z
review text: An alphabetic cone is a family of forests stable under alphabetic tree transductions, whereas we call REC-closed each family of forests closed under the operations of union, top-catenation, \(a\)-product and \(a\)-star; the sheaves are families having both the above properties. For a given sheaf of forests \(\mathcal F\), both the families of languages \(\text{Br}({\mathcal F})\) and \(\text{yield}({\mathcal F})\) (of branches and yields of \(\mathcal F\), respectively) constitute full AFL's. Further, we show the family K-REC of forests supporting recognizable formal power series on trees is a sheaf and so is the family OCF of behaviors of one-counter tree-automata. On the contrary, restricted on- counter forests (ROCF) constitute an alphabetic cone which fails to be a sheaf; \(\text{ROCF}_ N\) (restricted one-counter forests over alphabets with degree \(\leq N\)) is alphabetically principal generated by the Łukasiewicz forest of rank \(N\).
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 567338
zbMATH Keywords: alphabetic cone
zbMATH Keywords: family of forests
zbMATH Keywords: alphabetic tree transductions
zbMATH Keywords: sheaves
zbMATH Keywords: tree-automata
MaRDI profile type: Publication
cites work: Indexed Grammars—An Extension of Context-Free Grammars
cites work: Weighted grammars and Kleene's theorem
cites work: Un théorème de Chomsky-Schützenberger pour les forets algébriques
cites work: Forêts Algébriques et Homomorphismes Inverses
cites work: Une propri\'et\'e des forêts alg\'ebriques « de greibach \ra
cites work: Q3995871
cites work: Q3859267
cites work: Recognizable formal power series on trees
cites work: Q3994777
cites work: Représentations matricielles des séries d'arbre reconnaissables
cites work: Effective construction of the syntactic algebra of a recognizable series on trees
cites work: Alphabetic tree relations
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: Q3323279
cites work: Q4089754
cites work: Studies in abstract families of languages
cites work: Pushdown tree automata
cites work: A generalized approach to formal languages
cites work: Mappings and grammars on trees
cites work: Q4155837
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
full work available at URL: https://doi.org/10.1007/bf01218405
OpenAlex ID: W2081386906
description: scientific article; zbMATH DE number 567338