A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A note on decidability questions on presentations of word semigroups
Tekijät: Choffrut C, Harju T, Karhumaki J
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 1997
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 183
Numero: 1
Aloitussivu: 83
Lopetussivu: 92
Sivujen määrä: 10
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(96)00311-8
Tiivistelmä
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.
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.
Turun yliopiston Tutkimustietojärjestelmän portaali