Résumé
Nous étendons le théorème de Reiterman aux structures du premier ordre: une classe de structures du premier ordre finies est une pseudovariété si et seulement si elle est définie par un ensemble d'identités dans une structure profinie relativement libre (pseudoidentités).
Abstract
We extend Reiterman's theorem to first-order structures: a class of finite first-order structures is a pseudovariety if and only if it is defined by a set of identities in a certain relatively free profinite structure (pseudoidentities).
This is a preview of subscription content, log in via an institution to check access.
References
Almeida, J.,Finite Semigroups and Universal Algebra, World Scientific, Singapore, 1994.
Almeida, J. andWeil, P.,Relatively free profinite monoids: an introduction and examples, in J. Fountain, ed.Semigroups, Formal Languages and Groups, NATO ASI Series C-466, Kluwer Academic Publishers, 1995, 73–117.
Almeida, J. andWeil, P.,Free profinite semigroups over semidirect products, Izvest. vuz. Matem.39 (1995), 3–31. English version: Russian Maths. (Iz. VUZ)39 (1995), 1–28.
Bloom, S.,Varieties of ordered algebras, J. Computer System Sciences13 (1976), 200–212.
Burris, S. andSankappanavar, H. P.,A Course in Universal Algebra, Undergraduate Texts in Mathematics78, Springer, 1981.
Ehrig, H. andMahr, B.,Fundamentals of algebraic specification 1, EATCS Monographs on Theoretical Computer Science6, Springer, Berlin, 1985.
Gorbunov, V. andTumanov, V.,Structure of lattices of quasivarieties, Dokl. AN SSSR254 (1980), 272–275. English transl. Soviet Math. Dokl.22 (1980), 333–336.
Kanellakis, P.,Elements of relational database theory, in J. van Leeuwen, ed.,Handbook of Theoretical Computer Science, Elsevier, Amsterdam, 1990, pp. 1073–1156.
Keisler, H. J.,Fundamentals of model theory, in J. Barwise, ed.,Handbook of Mathematical Logic, North Holland, Amsterdam, 1977, pp. 47–104.
Mal'cev, A. I.,Algebraic Systems, Grundlehren der mathematischen Wissenschaften192, Springer, 1973.
Perrin, D. andPin, J.-E.,Semigroups and automata on infinite words, in J. Fountain ed.Semigroups, Formal Languages and Groups, NATO ASI Series C-466, Kluwer Academic Publishers, 1995, 49–72.
Pin, J.-E.,Eilenberg's theorem for positive varieties of languages, Izvest. vuz. Matem.39 (1995), 80–90. English version: Russian Maths. (Iz. VUZ)39 (1995), 74–83.
Pin, J.-E. andWeil, P.,Polynomial closure and unambiguous product, to appear. Technical Report LITP 94-60, Paris.
Reiterman, J.,The Birkhoff theorem for finite algebras, Algebra Universalis14 (1982), 1–10.
Wechler, W.,Universal Algebra for Computer Scientists, EATCS Monographs on Theoretical Computer Science25, Springer, Berlin, 1992.
Wilke, T.,An algebraic theory for regular languages of finite and infinite words, Intern. J. Algebra Comput.3 (1993), 447–489.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pin, J.E., Weil, P. A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis 35, 577–595 (1996). https://doi.org/10.1007/BF01243597
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01243597