Markov semigroups, monoids and groups.
type: Item
instance of: scholarly article
zbMATH Open document ID: 1325.20055
DOI: 10.1142/S021819671450026X
author: Alan J. Cain
author: Victor Maltcev
published in: International Journal of Algebra and Computation
publication date: 2014-10-15T00:00:00Z
full work available at URL: https://arxiv.org/abs/1202.3013
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6356167
zbMATH Keywords: Markov monoids
zbMATH Keywords: Markov semigroups
zbMATH Keywords: regular languages
zbMATH Keywords: prefix-closed languages
zbMATH Keywords: rewriting systems
zbMATH Keywords: normal form theorems
zbMATH Keywords: word hyperbolic semigroups
zbMATH Keywords: finite generating sets
MaRDI profile type: Publication
arXiv ID: 1202.3013
cites work: Malcev presentations for subsemigroups of direct products of coherent groups.
cites work: Green index in semigroups: generators, presentations, and automatic structures.
cites work: CONTEXT-FREE REWRITING SYSTEMS AND WORD-HYPERBOLIC STRUCTURES WITH UNIQUENESS
cites work: Finitely presented monoids with linear Dehn function need not have regular cross-sections.
cites work: Automatic presentations for semigroups.
cites work: Automatic semigroups
cites work: Remarks concerning finitely generated semigroups having regular sets of unique normal forms
cites work: Commutative monoids have complete presentations by free (non-commutative) monoids
cites work: Word hyperbolic semigroups
cites work: Automatic monoids and change of generators
cites work: A context-free and a 1-counter geodesic language for a Baumslag-Solitar group
cites work: Green index and finiteness conditions for semigroups.
cites work: On problems related to growth, entropy, and spectrum in group theory
cites work: A short proof of Rédei's theorem
cites work: Minimal length normal forms for some soluble groups
cites work: AUTOMATIC SEMIGROUPS WITH SUBSEMIGROUPS OF FINITE REES INDEX
cites work: Q3862379
cites work: Uniform decision problems for automatic semigroups.
cites work: On monoids presented by a single relation
cites work: CAYLEY AUTOMATON SEMIGROUPS
cites work: Regular geodesic normal forms in virtually Abelian groups
cites work: Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
cites work: Generators and relations of direct products of semigroups
cites work: Q4951130
cites work: Syntactic and Rees indices of subsemigroups
cites work: ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
cites work: A finiteness condition for rewriting systems
cites work: Rational and transcendental growth series for the higher Heisenberg groups
OpenAlex ID: W2000596726
Recommended article: Semigroups, rings, and Markov chains
Recommended article: Q3462066
Recommended article: Q4463714
Recommended article: Q4449372
Recommended article: Q4657002
Recommended article: Q3108270
Recommended article: Q4435812
Recommended article: Markov processes, semigroups and generators.
Recommended article: Hyperaction of semigroups and monoids.
title: Markov semigroups, monoids and groups.
review text: The authors extend the notions of a Markov/strongly Markov group to monoids and semigroups. Let \(M\) be a monoid and \(A\) its finite generating set. A Markov language for \(M\) over \(A\) is a regular prefix-closed language \(L\subseteq A^*\) that contains a unique representative for every element of \(M\). Additionally, if, for each \(x\in M\), the length of its representative in \(L\) is equal to the length of the shortest word over \(A\) representing \(x\), then \(L\) is called robust. A monoid \(M\) is (robustly) Markov with respect to a finite generating set \(A\) if there exists a (robust) Markov language for \(M\) over \(A\), and \(M\) is strongly Markov if, for every finite generating set \(A\) for \(M\), there exists a robust Markov language for \(M\) over \(A\). The definitions apply to the semigroup case mutatis mutandis; for instance, \(L\) should exclude the empty word in that case. The authors verify that for monoids the monoid and the semigroup versions of these definitions are equivalent.NEWLINENEWLINE The paper contains several results and examples that aim at clarifying the relations between Markov and strongly Markov monoids and other classes of finitely generated monoids specified by certain properties of their languages of representatives. In particular, the authors exhibit a non-Markov monoid that admits a regular language of unique representatives over any finite generating set and show that the classes of Markov, robustly Markov and strongly Markov monoids are distinct. If \(\langle A,\mathcal R\rangle\) is a confluent Noetherian rewriting system such that the set of left-hand sides of rewriting rules in \(\mathcal R\) is regular, then the presentation \(\langle A\mid\mathcal R\rangle\) defines a Markov monoid, and its language of normal forms is a Markov language. Finitely generated commutative semigroups are strongly Markov but there exists a virtually abelian group with a non-Markov subsemigroup. The authors also study closure properties…
description: scientific article; zbMATH DE number 6356167