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

DOI10.1017/S1446788723000010MaRDI QIDQ6065367zbMATH OpenFDO

Authors Carl-Fredrik Nyberg-Brodda

Publication date 14 November 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

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)