Thue system
From Encyclopedia of Mathematics
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
An associative calculus, named after A. Thue, who first formulated the problem of recognizing equality of words in associative systems (the Thue problem, see [1]). If in a given Thue system the only admissible substitutions are taken to be substitutions of right-hand sides of relations into the left-hand sides (that is, the reverse substitutions are excluded), then one obtains a Thue semi-system (or semi-Thue system, or system of substitutions). These systems in fact coincide with local canonical Post systems. Every Thue system can be regarded as a Thue semi-system, but the converse is false.
References
| [1] | A. Thue, "Probleme über Veränderungen von Zeichenreihen nach gegebener Regeln" Kra. Vidensk. Selsk. Skrifter. , 10 (1914) |
| [2] | A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian) |
How to Cite This Entry:
Thue system. S.I. Adyan (originator), Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Thue_system&oldid=18164
Thue system. S.I. Adyan (originator), Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Thue_system&oldid=18164
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098