Band monoid languages revisited (Q1576298)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Band monoid languages revisited |
scientific article |
Statements
Band monoid languages revisited (English)
0 references
18 April 2001
0 references
\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.
0 references
formal language varieties
0 references
band varieties
0 references
free bands
0 references
slim words
0 references
rewriting systems
0 references
confluence
0 references