Varieties of recognizable tree series over fields
type: Item
instance of: scholarly article
title: Varieties of recognizable tree series over fields
zbMATH Open document ID: 1220.68067
author: Zoltán Fülöp
author: Magnus Steinby
published in: Theoretical Computer Science
publication date: 2011-02-21T00:00:00Z
review text: For a field \(K\) and a (finite) ranked alphabet \(\Sigma\) and a leaf alphabet (i.e., a finite set of variables) \(X\), a tree series (or a \(K\Sigma X\)-series) is a mapping from the term algebra \(T_\Sigma(X)\) to \(K\). To each tree series, a special \(K\Sigma\)-algebra (called its syntactic \(K\Sigma\)-algebra) is associated; a \(\Sigma K\)-algebra is a \(K\)-vector space equipped with multi-linear \(\Sigma\)-operations (i.e., a \(\Sigma\)-algebra whose every \(\Sigma\)-operation is linear in all components). A tree series is recognizable if (and only if) its syntactic algebra is finite dimensional. A variety of tree series is a family \({\mathcal V}=\{{\mathcal V}(X)\}\), where \(X\) ranges over all leaf alphabets, such that for each \(X\), the class \({\mathcal V}(X)\) is a \(K\)-vector space of recognizable \(K\Sigma X\)-series closed under inverse translations and inverse homomorphisms. A variety of finite dimensional \(K\Sigma\)-algebras is a class closed under subalgebras, homomorphic images and direct products of finite families of algebras. The main result of the paper is a variety theorem that establishes a bijection between varieties of tree (\(K\Sigma X\)-)series and varieties of finite dimensional \(K\Sigma\)-algebras. Some interesting examples are presented at the end. The authors note that another theory of varieties of tree series has been proposed in [\textit{S. Bozapalidis} and \textit{S. Ioulidis}, ``Varieties of formal series on trees and Eilenberg's theorem'', Inf. Process. Lett. 29, No. 4, 171--175 (1988; Zbl 0658.08002)] with no (concrete) examples, and since that approach is quite different from the authors', the two theories have not been compared in the present paper.
reviewed by: Saeed Salehi
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5853807
zbMATH Keywords: tree languages
zbMATH Keywords: tree series
zbMATH Keywords: varieties of tree series
zbMATH Keywords: \(K\Sigma\)-algebras
zbMATH Keywords: syntactic algebras
zbMATH Keywords: variety theorem
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.11.018
OpenAlex ID: W1983225303
cites work: On pseudovarieties, varieties of languages, filters of congruences, pseudoidentities and related topics
cites work: Recognizable formal power series on trees
cites work: Q3994777
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: Varieties of formal series on trees and Eilenberg's theorem
cites work: On the syntactic complexity of tree series
cites work: The rank of a formal tree power series
cites work: Q3934450
cites work: Q5515373
cites work: Q4079524
cites work: Q4132170
cites work: A variety theorem for trees and theories
cites work: Q4449537
cites work: Q3655364
cites work: A characterization of attributed tree transformations by a subclass of macro tree transducers
cites work: Q4179852
cites work: Q4359479
cites work: Q4714446
cites work: Q3704880
cites work: Definable Transductions and Weighted Logics for Texts
cites work: Existential MSO over two successors is strictly weaker than over linear orders
cites work: Positive varieties of tree languages
cites work: Q3769981
cites work: Series formelles et algèbres syntactiques
cites work: Q4155837
cites work: Q5626549
cites work: Q4273660
cites work: Q3365845
DOI: 10.1016/J.TCS.2010.11.018
description: scientific article; zbMATH DE number 5853807