Confluence problems for trace rewriting systems

DOI10.1006/inco.2001.3055zbMath1007.68088OpenAlexW2014395024MaRDI QIDQ1854457

Markus Lohrey

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ec203c5578637ecb694ef77e89314ddfe1852c3a

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite complete rewriting systems and the complexity of word problem
• Word problems over traces which are solvable in linear time
• An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• Testing for the Church-Rosser property
• Combinatorics on traces
• Membership problems for regular and context-free trace languages
• On theories with a combinatorial definition of 'equivalence'
• Trace rewriting: Computing normal forms in time O(n log n)
• On confluence of one-rule trace-rewriting systems

This page was built for publication: Confluence problems for trace rewriting systems