The undecidability of the preperfectness of Thue systems
From MaRDI portal
Publication:797574
DOI10.1016/0304-3975(84)90133-6zbMath0545.03022OpenAlexW2027868924MaRDI QIDQ797574
Paliath Narendran, Robert McNaughton
Publication date: 1984
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(84)90133-6
monoidsThue systemsChurch-Rosser systemsalmost-confluent systemsemptiness problem for deterministic linear-bounded automatapreperfect systemsstring replacement systems
Undecidability and degrees of sets of sentences (03D35) Automata and formal grammars in connection with logical questions (03D05) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)
Related Items
On the regular equivalence problem for regular Thue systems, The undecidability of self-embedding for finite semi-Thue and Thue systems, 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, The word problem for free partially commutative groups, On confluence of one-rule trace-rewriting systems, Trace monoids with some invertible generators: Two decision problems, On deciding confluence of finite string-rewriting systems modulo partial commutativity, Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
Cites Work
