Bibliography | Diekert, Volker; Matiyasevich, Yuri; Muscholl, Anca: Solving Trace Equations Using Lexicographical Normal Forms. University of Stuttgart, Faculty of Computer Science, Technical Report No. 1997/01. 17 pages, english.
|
CR-Schema | F.m (Theory of Computation Miscellaneous)
|
Abstract | Very recently, Matiyasevich showed that the question whether an equation over a trace monoid has a solution or not is decidable. In his proof this question is reduced to the solvability of word equations with constraints, by induction on the size of the commutation relation. In the present paper we give another proof of this result using lexicographical normal forms. Our method is a direct reduction of a trace equation system to a word equation system with regular constraints. We use for this a new result on lexicographical normal forms.
|
Full text and other links | HTML (generated from PostScript)
|
Department(s) | University of Stuttgart, Institute of Computer Science, Theoretical Computer Science
|
Entry date | January 31, 1997 |
---|