The Church-Rosser property and special Thue systems

DOI10.1016/0304-3975(85)90134-3zbMath0586.03028OpenAlexW2053388467MaRDI QIDQ1071759

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

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)90134-3

zbMATH Keywords

pattern matchingcomplexity boundword equationalgorithm for testing the Church-Rosser property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Abstract data types; algebraic specification (68Q65) Semigroups in automata theory, linguistics, etc. (20M35) Thue and Post systems, etc. (03D03)

Related Items (5)

Complexity of certain decision problems about congruential languages ⋮ On the regular equivalence problem for regular Thue systems ⋮ The Church-Rosser property and special Thue systems ⋮ Complexity results on the conjugacy problem for monoids ⋮ A finite Thue system with decidable word problem and without equivalent finite canonical system

Cites Work

• An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
• The Church-Rosser property and special Thue systems
• Testing for the Church-Rosser property
• A note on special thue systems with a single defining relation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Church-Rosser property and special Thue systems