Namespaces
Variants
Actions

Thue system

From Encyclopedia of Mathematics
Revision as of 17:24, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098