Algèbre des termes
(Redirigé depuis Algèbre de termes)
En logique mathématique, l'algèbre des termes est la structure algébrique libre sur une signature[1],[2].
Exemples modifier
Si la signature ne contient qu'un symbole de fonction binaire f, alors l'algèbre des termes sur un ensemble de variables X est exactement le magma libre sur X. Si x, y, z sont des variables de X, cette algèbre des termes contient les éléments suivants : x, y, z, f(x, x), f(x, f(x, y)), f(f(f(y, f(x), f(z, z)), y, x), etc.
Décidabilité modifier
Le problème de décision associé[pas clair] à l'algèbre des termes est décidable et non élémentaire.
Références modifier
- (en) Wilifrid Hodges, A Shorter Model Theory, Cambridge, Cambridge University Press, , 14 p. (ISBN 978-0-521-58713-6, BNF 37534833)
- (en) Franz Baader et Tobias Nipkow, Term Rewriting and All That, Cambridge (GB), Cambridge University Press, , 49 p. (ISBN 978-0-521-77920-3, BNF 37566747)
