An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems

DOI10.1016/0304-3975(85)90008-8zbMath0563.03018OpenAlexW2080604675MaRDI QIDQ1057263

Paliath Narendran, Deepak Kapur, Mukkai S. Krishnamoorthy, Robert McNaughton

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90008-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Thue and Post systems, etc. (03D03)

Related Items (13)

Thue systems as rewriting systems ⋮ On deciding the confluence of a finite string-rewriting system on a given congruence class ⋮ Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule ⋮ A note on thue systems with a single defining relation ⋮ The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems ⋮ On public-key cryptosystem based on Church-Rosser string-rewriting systems ⋮ Confluence of one-rule Thue systems ⋮ The context-splittable normal form for Church-Rosser language systems. ⋮ Church-Rosser codes ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Confluence problems for trace rewriting systems ⋮ Lambda-confluence for context rewriting systems ⋮ The Church-Rosser property and special Thue systems

Cites Work

• Unnamed Item
• Testing for the Church-Rosser property
• On Proving Uniform Termination and Restricted Termination of Rewriting Systems
• Confluent and Other Types of Thue Systems
• Efficient string matching

This page was built for publication: An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems