The Church-Rosser property and special Thue systems

DOI10.1016/0304-3975(85)90134-3zbMath0586.03028MaRDI 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 matching; complexity bound; word equation; algorithm for testing the Church-Rosser property

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

20M05: Free semigroups, generators and relations, word problems

68Q65: Abstract data types; algebraic specification

20M35: Semigroups in automata theory, linguistics, etc.

03D03: Thue and Post systems, etc.

Related Items

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, Complexity of certain decision problems about congruential languages, On the regular equivalence problem for regular Thue systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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