Beitrag in einem Tagungsband
PDT is undecidable for finitely presented monoids with solvable word problems



Details zur Publikation
Autor(inn)en:
Otto, F.
Herausgeber:
Chlebus, EB; Czaja, L
Verlag:
Springer
Verlagsort / Veröffentlichungsort:
Berlin
Publikationsjahr:
1997
Seitenbereich:
388-399
Buchtitel:
FUNDAMENTALS OF COMPUTATION THEORY, PROCEEDINGS;INFORMATION AND COMPUTATION
Jahrgang/Band:
1279
Erste Seite:
388
Letzte Seite:
399
ISBN:
3-540-63386-3
ISSN:
0302-9743

Zusammenfassung, Abstract
Exploiting a new technique for proving undecidability results developed by A. Sattler-Klein in her doctoral dissertation (1996) it is shown that it is undecidable in general whether or not a finitely presented monoid with a solvable word problem has finite derivation type (FDT). This improves upon the undecidability result of R. Cremanns and F. Otto (1996), which was based on the undecidability of the word problem for the finitely presented monoids considered.


Autor(inn)en / Herausgeber(innen)

Zuletzt aktualisiert 2019-25-07 um 17:12