Concrete algorithms for word problem and subsemigroup problem for\n semigroups which are disjoint unions of finitely many copies of the free\n monogenic semigroup

2015/03/23 by Nabilah Abughazalah, Abughazalah, Nabilah
Computer Science · #FOS: Mathematics #Group Theory (math.GR) #Natural Language Processing Techniques #Optimization and Search Problems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1503.06818

openalex publication_date 2015/03/23 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

Every semigroup which is a finite disjoint union of copies of the free mono-\ngenic semigroup (natural numbers under addition) has soluble word prob- lem and\nsoluble membership problem. Efficient algorithms are given for both problems.\n

Related

• The word problem for free adequate semigroups
• Space functions and complexity of the word problem in semigroups
• Word problem languages for completely regular semigroups
• Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x²=x³
• On disjoint unions of finitely many copies of the free monogenic semigroup