Markov semigroups, monoids and groups.

DOI10.1142/S021819671450026XzbMATH Open1325.20055arXiv1202.3013OpenAlexW2000596726MaRDI QIDQ2923337FDOQ2923337

Authors: Alan J. Cain, Victor Maltcev 

Publication date: 15 October 2014

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Abstract: A group is Markov if it admits a prefix-closed regular language of unique representatives with respect to some generating set, and strongly Markov if it admits such a language of unique minimal-length representatives over every generating set. This paper considers the natural generalizations of these concepts to semigroups and monoids. Two distinct potential generalizations to monoids are shown to be equivalent. Various interesting examples are presented, including an example of a non-Markov monoid that nevertheless admits a regular language of unique representatives over any generating set. It is shown that all finitely generated commutative semigroups are strongly Markov, but that finitely generated subsemigroups of virtually abelian or polycyclic groups need not be. Potential connections with word-hyperbolic semigroups are investigated. A study is made of the interaction of the classes of Markov and strongly Markov semigroups with direct products, free products, and finite-index subsemigroups and extensions. Several questions are posed.

Full work available at URL: https://arxiv.org/abs/1202.3013

Recommendations

• Semigroups, rings, and Markov chains
• scientific article; zbMATH DE number 6525973
• scientific article; zbMATH DE number 2069981
• scientific article; zbMATH DE number 2039031
• scientific article; zbMATH DE number 2144722
• scientific article; zbMATH DE number 5993931
• scientific article; zbMATH DE number 2006036
• Markov processes, semigroups and generators.
• Hyperaction of semigroups and monoids.

zbMATH Keywords

Markov semigroupsregular languagesnormal form theoremsrewriting systemsfinite generating setsprefix-closed languagesMarkov monoidsword hyperbolic semigroups

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• Title not available (Why is that?)
• A context-free and a 1-counter geodesic language for a Baumslag-Solitar group
• CAYLEY AUTOMATON SEMIGROUPS
• Automatic semigroups
• Uniform decision problems for automatic semigroups.
• Word hyperbolic semigroups
• Context-free rewriting systems and word-hyperbolic structures with uniqueness
• Automatic monoids and change of generators
• On problems related to growth, entropy, and spectrum in group theory
• Green index in semigroups: generators, presentations, and automatic structures.
• Green index and finiteness conditions for semigroups.
• Syntactic and Rees indices of subsemigroups
• Rational and transcendental growth series for the higher Heisenberg groups
• Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
• A finiteness condition for rewriting systems
• Generators and relations of direct products of semigroups
• A short proof of Rédei's theorem
• Automatic presentations for semigroups.
• Minimal length normal forms for some soluble groups
• AUTOMATIC SEMIGROUPS WITH SUBSEMIGROUPS OF FINITE REES INDEX
• Finitely presented monoids with linear Dehn function need not have regular cross-sections.
• On monoids presented by a single relation
• Remarks concerning finitely generated semigroups having regular sets of unique normal forms
• Malcev presentations for subsemigroups of direct products of coherent groups.
• Commutative monoids have complete presentations by free (non-commutative) monoids
• Regular geodesic normal forms in virtually Abelian groups

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Two applications of monoid actions to cross-sections
• Finitely presented monoids with linear Dehn function need not have regular cross-sections.

This page was built for publication: Markov semigroups, monoids and groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2923337)