Details

Autor(en) / Beteiligte

• Otto, Friedrich
• Sattler-Klein, Andrea
• Chlebus, Bogdan S.
• Czaja, Ludwik

Titel

FDT is undecidable for finitely presented monoids with solvable word problems

Ist Teil von

• Fundamentals of Computation Theory, 2005, p.388-399

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2005

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.