Band monoid languages revisited
type: Item
instance of: scholarly article
title: Band monoid languages revisited
zbMATH Open document ID: 0964.20042
DOI: 10.1007/PL00006013
published in: Semigroup Forum
publication date: 2001-04-18T00:00:00Z
review text: \textit{J.~Siekmann} and \textit{P.~Szabó} [Semigroup Forum 25, 83-110 (1982; Zbl 0493.68087)] have found a Noetherian and confluent rewriting system for the free band monoid \(FB(A)\) over an alphabet \(A\). The system consists of the two sets of rules: (1)~\(ww\to w\) for all \(w\in A^*\) and (2)~\(uvw\to uw\) for all \(u,v,w\in A^*\) such that the sets of letters occurring in the words \(u\), \(uv\) and \(w\) coincide. The authors call a word slim if it admits no application of the rule (2) and denote by \(\text{Slim}(u)\) the set of all slim words over \(A\) that are equal to \(u\) in \(FB(A)\). They prove that, for each \(u\in A^*\), the set \(\text{Slim}(u)\) is finite and has a least and a greatest element with respect to the partial order on \(A^*\) defined as the transitive closure of the rule (1). In particular, this gives a simple algebraic proof of the confluence of the system (1)-(2). Another application is a transparent description of the least language that contains a given word and is recognized by a band. Reviewer's remark: Though the paper makes a difficult reading because of several gaps and unfortunate typos, its results appear to be correct.
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1491099
zbMATH Keywords: formal language varieties
zbMATH Keywords: band varieties
zbMATH Keywords: free bands
zbMATH Keywords: slim words
zbMATH Keywords: rewriting systems
zbMATH Keywords: confluence
author: O. Neto
author: Helena Sezinando
MaRDI profile type: Publication
full work available at URL: pl00006013
OpenAlex ID: W2056656124
Recommended article: Trees, band monoids and formal languages
Recommended article: COMPLETE REWRITING SYSTEMS FOR CODIFIED SUBMONOIDS
Recommended article: Q3789793
Recommended article: On deciding whether a monoid is a free monoid or is a group
Recommended article: Equations over finite sets of words and equivalence problems in automata theory
Recommended article: Explicit left orders on free groups extending the lexicographic order on free monoids.
Recommended article: On languages over an alphabet interpreted in a boolean algebra
Recommended article: Complete rewriting systems and homology of monoid algebras
Recommended article: Reachability via Cooperating Morphisms
Recommended article: Q4272210
description: scientific article; zbMATH DE number 1491099