Commutative semigroups with a context-free word problem
The word problem of a finitely generated commutative semigroup is shown to be context-free if and only if this semigroup does not contain the free commutative semigroup on two generators as a subsemigroup, answering a question of Brough et al. An analogous characterization is established for monoids as well.
Authors
- Peter Kostolányi (ORCID: https://orcid.org/0000-0002-5474-8781)
Institutions
- Comenius University Bratislava (SK)
Publication Details
- Journal
- International Journal of Algebra and Computation
- Published
- 2025-02-04
- DOI
- https://doi.org/10.1142/s0218196725500092
- Primary Topic
- semigroups and automata theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00