On varieties of rational languages and variable length codes. II
type: Item
instance of: scholarly article
title: On varieties of rational languages and variable length codes. II
zbMATH Open document ID: 0598.20063
DOI: 10.1016/0022-4049(86)90111-8
author: S. W. Margolis
author: Jean-Éric Pin
published in: Journal of Pure and Applied Algebra
publication date: 1986-01-01T00:00:00Z
review text: [Part I, cf. the second author, ibid. 23, 169-196 (1982; Zbl 0481.20042).] The first main result states that if \({\mathcal V}\) is a *-variety of languages closed under product, then it is described by its finite prefix codes: this means that there is a class \({\mathcal C}\) of codes such that \({\mathcal V}\) is the smallest variety containing all \(C^*\), for C in \({\mathcal C}\). The second main result describes the languages of the *- variety corresponding to the variety of monoids V*W, where the *-variety associated to W is closed under concatenation of languages, and where V*W denotes the variety of monoids generated by the semi-direct products of monoids in V by monoids in W.
reviewed by: Christophe Reutenauer
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 94A45
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 3964196
zbMATH Keywords: *-variety of languages
zbMATH Keywords: finite prefix codes
zbMATH Keywords: variety of monoids
zbMATH Keywords: concatenation
MaRDI profile type: Publication
full work available at URL: 0022-4049(86)90111-8
OpenAlex ID: W4239470957
cites work: Q3677189
cites work: Q3714479
cites work: Q3877877
cites work: Q4132170
cites work: Q3673124
cites work: Regular semigroups with D=R as syntactic monoids of prefix codes
cites work: Cyclotomic polynomials and unions of groups
cites work: Q3853827
cites work: Sur le calcul du monoide syntaxique d'un sous monoide finiment engendre
cites work: Q3323300
cites work: On the syntactic transformation semigroup of a language generated by a finite biprefix code
cites work: On varieties of rational languages and variable-length codes
cites work: Q3922191
cites work: Q5184421
cites work: Q3960138
cites work: Q3776657
cites work: Q4403738
cites work: On a question of McNaughton and Papert
cites work: Q4093378
cites work: Families of recognizable sets corresponding to certain varieties of finite monoids
cites work: Aperiodic homomorphisms and the concatenation product of recognizable sets
cites work: Q3913600
cites work: Finite semigroup varieties of the form V*D
cites work: Decomposition and complexity of finite semigroups
description: scientific article; zbMATH DE number 3964196