Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-16T23:44:34.889Z Has data issue: false hasContentIssue false
  • English
  • Français

Flat algebras and the translation of universal Horn logic to equational logic

Published online by Cambridge University Press:  12 March 2014

Marcel Jackson
Marcel Jackson*
Affiliation:
La Trobe University, Department of Mathematics, Victoria 3086, Australia, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe which subdirectly irreducible flat algebras arise in the variety generated by an arbitrary class of flat algebras with absorbing bottom element. This is used to give an elementary translation of the universal Horn logic of algebras, partial algebras, and more generally still, partial structures into the equational logic of conventional algebras. A number of examples and corollaries follow. For example, the problem of deciding which finite algebras of some fixed type have a finite basis for their quasi-identities is shown to be equivalent to the finite identity basis problem for the finite members of a finiteiy based variety with definable principal congruences.

Keywords

Quasi-varietyuniversal Horn classflat algebraflat semilatticemembership problemsundecidabilitythe finite basis problemflat extension of a groupinverse semigroupClifford semigroupBrandt semigroupQ-universalagreeable semigroup
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 1 , March 2008 , pp. 90 - 128
Copyright
Copyright © Association for Symbolic Logic 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Adams, M., Adaricheva, K., Dziobiak, W., and Kravchenko, A., Open questions related to the problem of Birkhoff and Maltsev, Studia Logica, vol. 78 (2004), pp. 357–378.CrossRefGoogle Scholar
[2]Adams, M. and Dziobiak, W., The lattice of quasivarieties of undirected graphs, Algebra Universalis, vol. 47 (2002), pp. 7–11.CrossRefGoogle Scholar
[3]Andréka, H., Burmeister, P., and Nemeti, I., Quasivarieties of partial algebras. A unifying approach towards a two-valued model theory for partial algebras, Studia Scientiarum Mathematicarum Hungarica, vol. 16 (1983), pp. 325–372.Google Scholar
[4]Baker, K., McNulty, G., and Wang, J., An extension of Willard's finite basis theorem: Congruence meet-semidistributive varieties of finite critical depth, Algebra Universalis, vol. 52 (2004), pp. 289–302.CrossRefGoogle Scholar
[5]Baker, K. and Wang, J., Definable principal subcongruences, Algebra Universalis, vol. 47 (2002), pp. 145–151.CrossRefGoogle Scholar
[6]Bergman, C. and Slutzki, G., Complexity of some problems concerning varieties and quasi-varieties of algebras, SIAM Journal on Computing, vol. 30 (2000), pp. 359–382.CrossRefGoogle Scholar
[7]Bergman, G. M. (editor), Problem list from Algebra, lattices and varieties: A conference in honor of Walter Taylor, University of Colorado, 15–18 08 2004, Algebra Universalis, vol. 55 (2006), pp. 509–526.Google Scholar
[8]Bezhanishvili, G., Locally finite varieties, Algebra Universalis, vol. 46 (2001), pp. 531–548.CrossRefGoogle Scholar
[9]Burmeister, P., Partial algebras — survey of a unifying approach towards a two-valued model theory for partial algebras, Algebra Universalis, vol. 15 (1982), pp. 306–358.CrossRefGoogle Scholar
[10]Burmeister, P., A model theoretic oriented approach to partial algebras. Introduction to theory and application of partial algebras. Part I, Mathematical Research, vol. 32, Akademie-Verlag, Berlin, 1986.Google Scholar
[11]Burris, S. and Sankappanavar, H. P., A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78, Springer Verlag, 1980.Google Scholar
[12]Clark, D. M., Davey, B. A., Freese, R. S., and Jackson, M., Standard topological algebras: Syntactic and principal congruences and profiniteness, Algebra Universalis, vol. 52 (2004), pp. 343–376.CrossRefGoogle Scholar
[13]Clifford, A. H. and Preston, G. B., The Algebraic Theory of Semigroups, Volume 2, American Mathematical Society, Providence, RI, 1967.CrossRefGoogle Scholar
[14]Delić, D., Finite bases for flat graph algebras, Journal of Algebra, vol. 246 (2001), pp. 453–469.CrossRefGoogle Scholar
[15]Demel, J., Fast algorithms for finding a subdirect decomposition and interesting congruences of finite algebras, Kybernetika (Prague), vol. 18 (1982), pp. 121–130.Google Scholar
[16]Eilenberg, S. and Schützenberger, M. P., On pseudovarieties, Advances in Mathematics, vol. 19 (1976), pp. 413–418.CrossRefGoogle Scholar
[17]Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Fransisco, 1979.Google Scholar
[18]Howie, J. M., Fundamentals of Semigroup Theory, Oxford University Press, Oxford, 1995.CrossRefGoogle Scholar
[19]Jackson, M., Finiteness properties of varieties and the restriction to finite algebras, Semigroup Forum, vol. 70 (2005), pp. 159–187.CrossRefGoogle Scholar
[20]Jackson, M. and McKenzie, R., Interpreting graph colourability in finite semigroups, International Journal of Algebra and Computation, vol. 16 (2006), pp. 119–140.CrossRefGoogle Scholar
[21]Jackson, M. and Stokes, T., Agreeable semigroups, Journal of Algebra, vol. 266 (2003), pp. 393–417.CrossRefGoogle Scholar
[22]Jackson, M. and Stokes, T., Identities in the algebra of partial maps, International Journal of Algebra and Computation, vol. 16 (2006), pp. 1131–1159.CrossRefGoogle Scholar
[23]Jackson, M. and Trotta, B., The division relation in general algebra, 2007, manuscript.Google Scholar
[24]Ježek, J., Maróti, M., and McKenzie, R., Quasiequational theories of flat algebras, Czechoslovak Mathematical Journal, vol. 55 (2005), pp. 665–675.CrossRefGoogle Scholar
[25]Kad'ourek, J., On bases of identities of finite inverse semigroups with solvable subgroups, Semigroup Forum, vol. 67 (2003), pp. 317–343.CrossRefGoogle Scholar
[26]Kharlampovich, O. G. and Sapir, M. V., Algorithmic problems in varieties, International Journal of Algebra and Computation, vol. 5 (1995), pp. 379–602.CrossRefGoogle Scholar
[27]Kozik, M., On some complexity problems in finite algebras, Ph.D. thesis, Nashville, 2004.Google Scholar
[28]Lampe, W. A., McNulty, G. F., and Willard, R., Full duality among graph algebras andflat graph algebras, Algebra Universalis, vol. 45 (2001), pp. 311–334.Google Scholar
[29]Lawrence, J. and Willard, R., On finitely based groups and nonfinitely based quasivarieties, Journal of Algebra, vol. 203 (1998), pp. 1–11.CrossRefGoogle Scholar
[30]Leech, J., Inverse monoids with a natural semilattice ordering, Proceedings of the London Mathematical Society (3), vol. 70 (1995), pp. 146–182.CrossRefGoogle Scholar
[31]Maltsev, A. I., Algebraicheskie Systemi, Nauka Press, Moscow, 1970, English translation: Algebraic Systems, Academie-Verlag, Berlin 1973.Google Scholar
[32]McKenzie, R., The residual bounds of finite algebras, International Journal of Algebra and Computation, vol. 6 (1996), no. 1, pp. 1–28.CrossRefGoogle Scholar
[33]McKenzie, R., The residual bound of a finite algebra is not computable, International Journal of Algebra and Computation, vol. 6 (1996), no. 1, pp. 29–48.CrossRefGoogle Scholar
[34]McKenzie, R., Tarski's finite basis problem is undecidable, International Journal of Algebra and Computation, vol. 6 (1996), pp. 49–104.CrossRefGoogle Scholar
[35]McNulty, G. F., Fragments of first order logic, I: Universal Horn logic, this Journal, vol. 42 (1977), pp. 221–237.Google Scholar
[36]Nešetřil, J. and Pultr, A., On classes of relations and graphs determined by subobjects and factor objects, Discrete Mathematics, vol. 22 (1978), pp. 287–300.CrossRefGoogle Scholar
[37]Oates, S. and Powell, M. B., Identical relations in finite groups, Journal of Algebra, vol. 1 (1964), pp. 11–39.CrossRefGoogle Scholar
[38]Ol'shanskii, A. Y., Conditional identities of finite groups, Sibirskii Matematicheskii Zhurnal, vol. 15 (1974), pp. 1409–1413, English version in: Siberian Mathematical Journal, vol. 15 (1975), pp. 1000–1003.Google Scholar
[39]Sapir, M.V., The lattice of quasivarieties of semigroups, Algebra Universalis, vol. 21 (1985), pp. 172–180.CrossRefGoogle Scholar
[40]Sapir, M.V., Sur la propiété de base finie pour les pseudovariétés de semigroupes finis, Comptes Rendus de l'Académie des Sciences Paris. Série I, vol. 306 (1988), pp. 795–797.Google Scholar
[41]Sapir, M.V., Identities of finite inverse semigroups, International Journal of Algebra and Computation, vol. 3 (1993), pp. 115–124.CrossRefGoogle Scholar
[42]Schein, B. M., Restrictively multiplicative algebras of transformations, Izvestiya Vysshikh Ucheb-nykh Zavedenii Matematika, vol. 95 (1970), no. 4, pp. 91–102.Google Scholar
[43]Szekely, Z., Computational complexity of the finite membership problem forvarieties, International Journal of Algebra and Computation, vol. 12 (2002), pp. 811–823.CrossRefGoogle Scholar
[44]Volkov, M. V., The finite basis problem for finite semigroups, Scientiae Mathematicae Japonicae, vol. 53 (2001), pp. 171–199.Google Scholar
[45]Willard, R., On McKenzie's method, Periodica Mathematica Hungarica., vol. 32 (1996), pp. 149–165.CrossRefGoogle Scholar