On deciding the confluence of a finite string-rewriting system on a given congruence class

DOI10.1016/0022-0000(87)90017-1zbMATH Open0645.03033OpenAlexW2058267787MaRDI QIDQ1102946FDOQ1102946

Authors: Friedrich Otto 

Publication date: 1987

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(87)90017-1

Recommendations

• Some results on Green's relations for monoids presented by monadic string-rewriting systems
• The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
• Decision problems for finite special string-rewriting systems that are confluent on some congruence class
• scientific article; zbMATH DE number 789389
• scientific article; zbMATH DE number 177883
• On weakly confluent monadic string-rewriting systems
• Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
• Some properties of finite special string-rewriting systems
• The word matching problem is undecidable for finite special string-rewriting systems that are confluent
• Reachability in Unions of Commutative Rewriting Systems Is Decidable

zbMATH Keywords

confluenceword problemstring-rewriting systemmembership problem

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Free semigroups, generators and relations, word problems (20M05) Theory of computing (68Q99) Word problems, etc. in computability and recursion theory (03D40)

Cites Work

• Title not available (Why is that?)
• On theories with a combinatorial definition of 'equivalence'
• Title not available (Why is that?)
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Title not available (Why is that?)
• Title not available (Why is that?)
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• The equivalence problem for deterministic finite-turn pushdown automata
• Title not available (Why is that?)
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Complexity of certain decision problems about congruential languages
• A note on a special one-rule semi-Thue system
• Title not available (Why is that?)
• Confluent and Other Types of Thue Systems
• Testing for the Church-Rosser property
• Monadic Thue systems
• Infinite regular Thue systems
• Some undecidability results for non-monadic Church-Rosser Thue systems
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Finite canonical rewriting systems for congruences generated by concurrency relations
• Finite complete rewriting systems and the complexity of word problem
• A note on special thue systems with a single defining relation
• An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
• Cancellativity in finitely presented semigroups
• On Proving Uniform Termination and Restricted Termination of Rewriting Systems
• Title not available (Why is that?)
• A note on thue systems with a single defining relation

Cited In (24)

• On weakly confluent monadic string-rewriting systems
• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• Algorithms and reductions for rewriting problems
• Lambda-confluence is undecidable for clearing restarting automata
• Decision problems for finite special string-rewriting systems that are confluent on some congruence class
• Completing a finite special string-rewriting system on the congruence class of the empty word
• Some properties of finite special string-rewriting systems
• Lambda-confluence for context rewriting systems
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Using string-rewriting for solving the word problem for finitely presented groups
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• The Knuth-Bendix algorithm and the conjugacy problem in monoids.
• Complexity of certain decision problems about congruential languages
• Reducing the gradedness problem of string rewriting systems to a termination problem
• About the descriptive power of certain classes of finite string-rewriting systems
• Some decision problems about controlled rewriting systems
• On Simon's congruence closure of a string
• The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
• It is decidable whether a monadic thue system is canonical over a regular set
• Restrictions of congruences generated by finite canonical string-rewriting systems
• Infinite Families of Finite String Rewriting Systems and Their Confluence
• The pre-NTS property is undecidable for context-free grammars
• Title not available (Why is that?)

This page was built for publication: On deciding the confluence of a finite string-rewriting system on a given congruence class

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102946)