The Finiteness of Finitely Presented Monoids Robert McNaughton It is undecidable whether a monoid given by a finite presentation is finite (see, e.g., [1], pp. 157{160). On the other hand, with the mere knowledge that the monoid is finite, one can effectively construct the multiplication table of the monoid, and thus obtain a complete understanding of its structure. This paper will present this construction method in detail (Section 2) and offer some remarks about its computational complexity (Section 3). The notation here will be based on [1], whose final chapter furnishes much of the background and will be referenced frequently. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-97-02
The Finiteness of Finitely Presented Monoids
Robert McNaughton
It is undecidable whether a monoid given by a finite presentation is finite (see, e.g., [1], pp. 157{160). On the other hand, with the mere knowledge that the monoid is finite, one can effectively construct the multiplication table of the monoid, and thus obtain a complete understanding of its structure. This paper will present this construction method in detail (Section 2) and offer some remarks about its computational complexity (Section 3). The notation here will be based on [1], whose final chapter furnishes much of the background and will be referenced frequently.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-97-02