2021/12/20 by Carl‐Fredrik Nyberg‐Brodda, Nyberg-Brodda, Carl-Fredrik
Computer Science · Mathematics · #20M05 (primary) 20F10 #20M35 #68Q45 (secondary) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Geometric and Algebraic Topology #Group Theory (math.GR) #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2112.10665
openalex publication_date 2021/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the language-theoretic aspects of the word problem, in the sense of Duncan & Gilman, of free products of semigroups and monoids. First, we provide algebraic tools for studying classes of languages known as super-AFLs, which generalise e.g. the context-free or the indexed languages. When C is a super-AFL closed under reversal, we prove that the semigroup (monoid) free product of two semigroups (resp. monoids) with word problem in C also has word problem in C. This recovers and generalises a recent result by Brough, Cain & Pfeiffer that the class of context-free semigroups (monoids) is closed under taking free products. As a group-theoretic corollary, we deduce that the word problem of the (group) free product of two groups with word problem in C is also in C. As a particular case, we find that the free product of two groups with indexed word problem has indexed word problem.