×

A Reiterman theorem for pseudovarieties of finite first-order structures. (English) Zbl 0864.03024

Birkhoff’s Theorem on classes of algebras being varieties was generalized by J. Reiterman as follows: a class of finite algebras is a pseudovariety (that is, it is closed under taking subalgebras, homomorphic images and finitary direct products) iff it is defined by a set of equations in the appropriate free profinite structures. Here, the result is generalized to first-order structures: under certain natural conditions of finiteness and non-emptiness, pseudovarieties of first-order structures are defined by relational identities (pseudoidentities) in some relatively free profinite structures.

MSC:

03C05 Equational classes, universal algebra in model theory
08B05 Equational logic, Mal’tsev conditions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Almeida, J.,Finite Semigroups and Universal Algebra, World Scientific, Singapore, 1994. · Zbl 0844.20039
[2] 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. · Zbl 0877.20038
[3] 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. · Zbl 0847.20055
[4] Bloom, S.,Varieties of ordered algebras, J. Computer System Sciences13 (1976), 200-212. · Zbl 0337.06008 · doi:10.1016/S0022-0000(76)80030-X
[5] Burris, S. andSankappanavar, H. P.,A Course in Universal Algebra, Undergraduate Texts in Mathematics78, Springer, 1981.
[6] Ehrig, H. andMahr, B.,Fundamentals of algebraic specification 1, EATCS Monographs on Theoretical Computer Science6, Springer, Berlin, 1985.
[7] Gorbunov, V. andTumanov, V.,Structure of lattices of quasivarieties, Dokl. AN SSSR254 (1980), 272-275. English transl. Soviet Math. Dokl.22 (1980), 333-336.
[8] Kanellakis, P.,Elements of relational database theory, in J. van Leeuwen, ed.,Handbook of Theoretical Computer Science, Elsevier, Amsterdam, 1990, pp. 1073-1156. · Zbl 0900.68090
[9] Keisler, H. J.,Fundamentals of model theory, in J. Barwise, ed.,Handbook of Mathematical Logic, North Holland, Amsterdam, 1977, pp. 47-104.
[10] Mal’cev, A. I.,Algebraic Systems, Grundlehren der mathematischen Wissenschaften192, Springer, 1973.
[11] 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.
[12] 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. · Zbl 0852.20059
[13] Pin, J.-E. andWeil, P.,Polynomial closure and unambiguous product, to appear. Technical Report LITP 94-60, Paris. · Zbl 0872.68119
[14] Reiterman, J.,The Birkhoff theorem for finite algebras, Algebra Universalis14 (1982), 1-10. · Zbl 0484.08007 · doi:10.1007/BF02483902
[15] Wechler, W.,Universal Algebra for Computer Scientists, EATCS Monographs on Theoretical Computer Science25, Springer, Berlin, 1992.
[16] Wilke, T.,An algebraic theory for regular languages of finite and infinite words, Intern. J. Algebra Comput.3 (1993), 447-489. · Zbl 0791.68116 · doi:10.1142/S0218196793000287
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.