The unification problem for one relation Thue systems

DOI10.1007/BFB0055913MaRDI QIDQ4217957zbMATH OpenFDO

Authors Christopher Lynch

Publication date 19 August 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0055913

zbMATH Keywords

algorithmsThue systemsunification

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Word problems, etc. in computability and recursion theory (03D40) Grammars and rewriting systems (68Q42)

Review text

The unification problem for Thue systems with one equation is defined as follows: given an equation set (with \(s\) and \(t\) words) and words \(u\) and \(v\), are there words \(x\) and \(y\) such that \(vy\) can be reached from \(ux\) with a sequence of replacements of \(s\) by \(t\) and \(t\) by \(s\). The paper considers a generalization of this problem by allowing more equations that satisfy some syntactical restrictions. An algorithm is presented that gives the correct answer provided that it halts. The author conjectures that it always halts. For the entire collection see [Zbl 0896.00032].

Recommendations

• On reduced thue systems
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Solving word equations
• A note on thue systems with a single defining relation
• Minimal and complete word unification

This page was built for publication: The unification problem for one relation Thue systems

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