A language theoretic interpretation of the Schützenberger representations with applications to certain varieties of languages
type: Item
instance of: scholarly article
title: A language theoretic interpretation of the Schützenberger representations with applications to certain varieties of languages
zbMATH Open document ID: 0542.20045
DOI: 10.1007/BF02572486
author: Denis Thérien
published in: Semigroup Forum
publication date: 1984-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/134652
review text: Let A be a finite set and \(A^+\) the free semigroup generated by A. A finite semigroup S recognizes the language \(X\subseteq A^+\) iff there exists a morphism \(\phi:A^+\to S\) such that X is the union of equivalence classes of the congruence \(\phi \phi^{-1}\). A class V of finite semigroups is called an S-variety (or a pseudovariety) if for any \(S,T\in V,\quad S\times T\in V\) and V contains all morphic images of subsemigroups of S. If V is an S-variety and \({\mathcal V}\) a class of subsets of \(A^+\), then \(V\leftrightarrow {\mathcal V}\) means that \({\mathcal V}\) consists of all languages \(X\subseteq A^+\) which are recognized by semigroups in V. M-varieties and G-varieties are defined similarly for monoids and groups respectively and the corresponding classes of recognizable languages consist of subsets of \(A^*\) (the free monoid generated by A). Using a graph theoretic interpretation of the Schützenberger representation of semigroups the author develops a general technique for describing languages in \({\mathcal V}\), \({\mathcal V}\leftrightarrow V\), when V is some special variety (in particular, a certain M-variety of unions of groups from the given G-variety or a certain S-variety of semigroups S such that eSe is in the given G-variety for all idempotents e of S).
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 3861453
zbMATH Keywords: free semigroup
zbMATH Keywords: finite semigroups
zbMATH Keywords: pseudovariety
zbMATH Keywords: languages
zbMATH Keywords: recognizable languages
zbMATH Keywords: Schützenberger representation of semigroups
zbMATH Keywords: unions of groups
zbMATH Keywords: idempotents
reviewed by: S. M. Goberstein
MaRDI profile type: Publication
cites work: Classification of noncounting events
cites work: Q4132170
cites work: Q3853827
cites work: Families of recognizable sets corresponding to certain varieties of finite monoids
description: scientific article; zbMATH DE number 3861453