A note on decidability questions on presentations of word semigroups



: Choffrut C, Harju T, Karhumaki J

Publisher: ELSEVIER SCIENCE BV

: 1997

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 183

: 1

: 83

: 92

: 10

: 0304-3975

DOI: https://doi.org/10.1016/S0304-3975(96)00311-8


We apply automata-theoretic tools and some recently established compactness properties in the study of F-semigroups, that is, subsemigroups of free semigroups. With each F-semigroup we associate an F-presentation, which turns out to be finite for all finitely generated F-semigroups. Connections between F-presentations and ordinary presentations of semigroups are pointed out. It is also shown that it is undecidable whether two finitely generated F-semigroups satisfy a common relation in their F-presentations.



Last updated on 2025-13-10 at 12:34