scientific article
From MaRDI portal
Publication:3939790
zbMath0482.03018MaRDI QIDQ3939790
Celia Wrathall, Burkhard Monien, Ronald V. Book, Matthias Jantzen, Colm P. O'Dunlaing
Publication date: 1981
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Church-Rosserreplacement systemclasses of Thue systems that have decidable word problemscontext-free monadic Thue systemsregular monadic Thue systems
Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)
Related Items (6)
A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems ⋮ Thue systems as rewriting systems ⋮ Rewriting systems and word problems in a free partially commutative monoid ⋮ Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule ⋮ Some undecidability results for non-monadic Church-Rosser Thue systems ⋮ Complexity results on the conjugacy problem for monoids
This page was built for publication:
