Varieties of recognizable tree series over fields

DOI10.1016/J.TCS.2010.11.018MaRDI QIDQ627171zbMATH OpenOpenAlexFDO

Authors Zoltán Fülöp, Magnus Steinby

Publication date 21 February 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.11.018

zbMATH Keywords

\(K\Sigma\)-algebras syntactic algebras tree languages tree series varieties of tree series variety theorem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Varieties of recognizable tree series over fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q627171)