Some undecidability results for non-monadic Church-Rosser Thue systems

DOI10.1016/0304-3975(84)90090-2zbMath0563.03019OpenAlexW1998439085MaRDI QIDQ1057264

Friedrich Otto

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)90090-2

zbMATH Keywords

Thue systemlinear sentence

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03)

Related Items (19)

On sufficient-completeness and related properties of term rewriting systems ⋮ The problems of cyclic equality and conjugacy for finite complete rewriting systems ⋮ Codes modulo finite monadic string-rewriting systems ⋮ Weights for total division orderings on strings ⋮ Restrictions of congruences generated by finite canonical string-rewriting systems ⋮ Thue systems as rewriting systems ⋮ On deciding the confluence of a finite string-rewriting system on a given congruence class ⋮ An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group ⋮ Some decision problems about controlled rewriting systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ When is an extension of a specification consistent? Decidable and undecidable cases ⋮ On weakly confluent monadic string-rewriting systems ⋮ Cancellation rules and extended word problems ⋮ A strong geometric hyperbolicity property for directed graphs and monoids. ⋮ Some undecidability results concerning the property of preserving regularity ⋮ Lambda-confluence for context rewriting systems ⋮ On two problems related to cancellativity ⋮ On deciding whether a monoid is a free monoid or is a group

Cites Work

• Decidable sentences of Church-Rosser congruences
• Monadic Thue systems
• When is a monoid a group? The Church-Rosser case is tractable
• Infinite regular Thue systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• The honest subrecursive classes are a lattice
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• FINITELY PRESENTED GROUP WHOSE WORD PROBLEM HAS THE SAME DEGREE AS THAT OF AN ARBITRARILY GIVEN THUE SYSTEM (AN APPLICATION OF METHODS OF BRITTON)
• Strong Computability and Variants of the Uniform Halting Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some undecidability results for non-monadic Church-Rosser Thue systems