A1 Refereed original research article in a scientific journal
A note on decidability questions on presentations of word semigroups
Authors: Choffrut C, Harju T, Karhumaki J
Publisher: ELSEVIER SCIENCE BV
Publication year: 1997
Journal:: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 183
Issue: 1
First page : 83
Last page: 92
Number of pages: 10
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(96)00311-8
Abstract
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.
UTU Research Portal