MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS

DOI10.1017/S1446788723000010arXiv2204.06492MaRDI QIDQ6065367FDOQ6065367

Authors: Carl-Fredrik Nyberg-Brodda 

Publication date: 14 November 2023

Published in: Journal of the Australian Mathematical Society (Search for Journal in Brave)

Abstract: This article studies the properties of word-hyperbolic semigroups and monoids, i.e. those having context-free multiplication tables with respect to a regular combing, as defined by Duncan & Gilman. In particular, the preservation of word-hyperbolicity under taking free products is considered. Under mild conditions on the semigroups involved, satisfied e.g. by monoids or regular semigroups, we prove that the semigroup free product of two word-hyperbolic semigroups is again word-hyperbolic. Analogously, with a mild condition on the uniqueness of representation for the identity element, satisfied e.g. by groups, we prove that the monoid free product of two word-hyperbolic monoids is word-hyperbolic. The methods are language-theoretically general, and apply equally well to semigroups, monoids, or groups with a $mathbfC$-multiplication table, where $mathbfC$ is any reversal-closed super-$operatornameAFL$, in the sense of Greibach. In particular, we deduce that the free product of two groups with $operatornameET0L$ resp. indexed multiplication tables again has an $operatornameET0L$ resp. indexed multiplication table.

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

Recommendations

• On the word problem for free products of semigroups and monoids
• Word hyperbolic semigroups
• Hyperbolic groups and completely simple semigroups.
• Context-free word problem semigroups
• Decision problems for word-hyperbolic semigroups

zbMATH Keywords

free producthyperbolic semigrouphyperbolic groupET0L languages

Mathematics Subject Classification ID

Hyperbolic groups and nonpositively curved groups (20F67) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• Géométrie et théorie des groupes. Les groupes hyperboliques de Gromov. (Geometry and group theory. The hyperbolic groups of Gromov)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The mathematical writings of Évariste Galois
• Title not available (Why is that?)
• Title not available (Why is that?)
• The strong equivalence of ET0L grammars
• Title not available (Why is that?)
• Indexed Grammars—An Extension of Context-Free Grammars
• On the definition of word hyperbolic groups.
• Decision problems for word-hyperbolic semigroups
• Hyperbolic groups and completely simple semigroups.
• Title not available (Why is that?)
• Word hyperbolic semigroups
• Semigroup and Group Presentations
• Context-free rewriting systems and word-hyperbolic structures with uniqueness
• The isomorphism problem for all hyperbolic groups.
• The accessibility of finitely presented groups
• Solution sets for equations over free groups are EDT0L languages
• A geometric characterization of automatic semigroups
• Title not available (Why is that?)
• Notions of hyperbolicity in monoids.
• Formal language theory and the geometry of 3-manifolds
• Title not available (Why is that?)
• Groups, the theory of ends, and context-free languages
• Title not available (Why is that?)
• Full AFLs and nested iterated substitution
• A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free
• Church-Rosser Thue systems and formal languages
• Title not available (Why is that?)
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Title not available (Why is that?)
• Three hierarchies of transducers
• Groups acting on semimetric spaces and quasi-isometries of monoids.
• Monadic Thue systems
• A relationship between ETOL and EDTOL languages
• Surface tree languages and parallel derivation trees
• Principal AFL
• Substitutions dans les EDT0L systèmes ultralinéaires
• Title not available (Why is that?)
• Studies in abstract families of languages
• Chains of full AFL's
• Branching synchronization grammars with nested tables
• Title not available (Why is that?)
• McNaughton families of languages.
• Title not available (Why is that?)
• On the word problem for special monoids
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• Amenability and geometry of semigroups
• A shrinking lemma for indexed languages
• Algebraic aspects of families of fuzzy languages
• Forbidding ET0L grammars.
• Ogden's lemma for ET0L languages
• A new pumping lemma for indexed languages, with an application to infinite words
• A Švarc-Milnor lemma for monoids acting by isometric embeddings.
• A strong geometric hyperbolicity property for directed graphs and monoids.
• Substitution in families of languages
• Title not available (Why is that?)
• A Geometric Characterization of Automatic Monoids
• Title not available (Why is that?)
• Hierarchies of hyper-AFLs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Controlled iteration grammars and full hyper-AFL's
• L systems
• On recursion in ETOL systems
• Title not available (Why is that?)
• A remark about a substitution property
• Title not available (Why is that?)
• Some Remarks on Semigroup Presentations
• Title not available (Why is that?)
• Bibliography of L systems
• On the word problem for free products of semigroups and monoids
• Applications of L systems to group theory
• Title not available (Why is that?)
• Permutations of context-free, ET0L and indexed languages
• On equations and first-order theory of one-relator monoids
• Equations in virtually abelian groups: Languages and growth
• Solutions to twisted word equations and equations in virtually free groups
• The complexity of solution sets to equations in hyperbolic groups
• Title not available (Why is that?)
• On the word problem for weakly compressible monoids
• Title not available (Why is that?)
• On cogrowth, amenability, and the spectral radius of a random walk on a semigroup
• Title not available (Why is that?)

Cited In (1)

• On ordered hypersemigroups given by a table of multiplication and a figure

This page was built for publication: MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS

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