Finite complete rewriting systems and the complexity of word problem

DOI10.1007/BF00271645zbMath0535.68019MaRDI QIDQ791314

Friedrich Otto, Günther Bauer

Publication date: 1984

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

word problemfinite complete rewriting systemfinite monoid presentations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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

SOME EXACT SEQUENCES FOR THE HOMOTOPY (BI-)MODULE OF A MONOID, A finiteness condition for rewriting systems, n-level rewriting systems, Some results on the confluence property of combined term rewriting systems, Complete semi-Thue systems for abelian groups, The problems of cyclic equality and conjugacy for finite complete rewriting systems, An equational logic sampler, Restrictions of congruences generated by finite canonical string-rewriting systems, Incremental termination proofs and the length of derivations, A catalogue of complete group presentations, Thue systems as rewriting systems, On deciding the confluence of a finite string-rewriting system on a given congruence class, History and basic features of the critical-pair/completion procedure, Complexity, combinatorial group theory and the language of palutators, Pseudo-natural algorithms for finitely generated presentations of monoids and groups, Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages, Reconfiguration in bounded bandwidth and tree-depth, On public-key cryptosystem based on Church-Rosser string-rewriting systems, For finitely presented monoids the homological finiteness conditions FHT and \(\text{bi-FP}_3\) coincide, Finite canonical rewriting systems for congruences generated by concurrency relations, About the descriptive power of certain classes of finite string-rewriting systems, On ground-confluence of term rewriting systems, Confluence of Graph Rewriting with Interfaces, The word problem for one-relation monoids: a survey, A field guide to equational logic, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS, A strong geometric hyperbolicity property for directed graphs and monoids., Confluence problems for trace rewriting systems, A note on a special one-rule semi-Thue system, Pseudo-natural algorithms for the word problem for finitely presented monoids and groups, String diagram rewrite theory III: Confluence with and without Frobenius

Cites Work

• Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• On the density of honest subrecursive classes
• Undecidable questions related to Church-Rosser Thue systems
• On theories with a combinatorial definition of 'equivalence'
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Strong Computability and Variants of the Uniform Halting Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item