Trees, band monoids and formal languages
type: Item
instance of: scholarly article
title: Trees, band monoids and formal languages
zbMATH Open document ID: 0851.20060
DOI: 10.1007/BF02574091
author: O. Neto
author: Helena Sezinando
published in: Semigroup Forum
publication date: 1996-05-19T00:00:00Z
full work available at URL: https://eudml.org/doc/135443
review text: The authors endow the free monoid \(\{e,s\}^*\) with the structure of a binary tree as follows: the left [right] son of a word \(\alpha\in\{e,s\}^*\) is the word \(s\alpha\) [resp. \(e\alpha\)]. A binary tree is called inertial if each left [right] son \(x\) has a left [right] son \(y\) and the binary trees of descendants of \(x\) and \(y\) are isomorphic. The lattice of all inertial subtrees of the binary tree \(\{e,s\}^*\) (including the empty subtree) is shown to be isomorphic to the lattice of all varieties of band monoids (Theorem 3.2). Let \(\Gamma(V)\) be the inertial subtree of \(\{e,s\}^*\) corresponding to a variety \(V\) of band monoids, \(A\) a set. A mapping \(\varphi\) assigning a subset of \(A\) to each vertex of \(\Gamma(V)\) is called admissible if \(\varphi(y)\) is obtained by removing an element from \(\varphi(x)\) whenever \(y\) is a son of \(x\) and \(\varphi(x)\) is non-empty. Then the set of all admissible mappings with a suitable multiplication yields a model for the \(A\)-generated relatively free monoid of the variety \(V\) (Theorem 3.8). Finally, the authors describe the atoms of the boolean algebra of \(V\)-recognizable languages over \(A\) (Theorem 4.5).
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 08B15
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 858469
zbMATH Keywords: lattices of varieties
zbMATH Keywords: recognizable languages
zbMATH Keywords: free monoids
zbMATH Keywords: binary trees
zbMATH Keywords: inertial subtrees
zbMATH Keywords: band monoids
MaRDI profile type: Publication
cites work: All varieties of bands
cites work: The lattice of equational classes of idempotent semigroups
cites work: Free bands and free *-bands
cites work: Varieties of Bands Revisited
cites work: Q3689384
cites work: The cardinalities of the Green classes of the free objects in varieties of bands
cites work: The varieties of languages corresponding to the varieties of finite band monoids
cites work: The lattices of varieties and pseudovarieties of band monoids
OpenAlex ID: W2028769549
Recommended article: CLASSES OF TREE LANGUAGES DETERMINED BY CLASSES OF MONOIDS
Recommended article: Inverse Monoids, Trees, and Context-Free Languages
Recommended article: Tree algebras and varieties of tree languages
Recommended article: Q5696196
Recommended article: Q4273659
Recommended article: Q4273669
Recommended article: Formations of Monoids, Congruences, and Formal Languages
Recommended article: Monodic Tree Kleene Algebra
Recommended article: Monoidal-closed categories of tree automata
Recommended article: Band monoid languages revisited
description: scientific article; zbMATH DE number 858469