Characterizations of several Maltsev conditions

详细信息    查看全文

• 作者：Marcin Kozik ; Andrei Krokhin ; Matt Valeriote ; Ross Willard
• 关键词：08B05 ; 08B10 ; 08A70 ; Maltsev condition ; variety
• 刊名：Algebra Universalis
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：73
• 期：3-4
• 页码：205-224
• 全文大小：439 KB
• 参考文献：1.Barto, L.: The collapse of the bounded width hierarchy. J. Logic Comput., to appear
  2.Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 595鈥?03. IEEE Computer Soc., Los Alamitos, CA (2009)
  3.Barto, L., Kozik, M.: Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Log. Methods Comput. Sci. 8(1), 1:07, 27 (2012)
  4.Barto, L., Kozik, M.: Constraint satisfaction problems solvable by local consistency methods. J. ACM 61(1), 3:1鈥?:19 (2014)
  5.Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38(5), 1782鈥?802 (2008/09)
  6.Barto, L., Kozik, M., Stanovsk媒, D.: Mal鈥檛sev conditions, lack of absorption, and solvability. Algebra Universalis, to appear (2014)
  7.Bergman, C.: Universal Algebra, Fundamentals and Selected Topics. Pure and Applied Mathematics (Boca Raton), vol. 301. CRC Press, Boca Raton (2012)
  8.Bulatov, A.A.: Bounded relational width (2009, preprint)
  9.Bulatov, A.A., Valeriote, M.: Recent results on the algebraic approach to the CSP. In: Creignou et聽al. [11]., pp. 68鈥?2
  10.Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78. Springer, New York (1981)
  11.Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.): Complexity of Constraints 鈥?An Overview of Current Research Themes Result of a Dagstuhl Seminar., Lecture Notes in Computer Science, vol. 5250. Springer (2008)
  12.Freese, R., McKenzie, R.: Maltsev families of varieties closed under join or Maltsev product (2013 preprint)
  13.Garc铆a, O.C., Taylor, W.: The lattice of interpretability types of varieties. Mem. Amer. Math. Soc. 50 (305) (1984)
  14.Hagemann, J., Mitschke, A.: On n-permutable congruences. Algebra Universalis 3, 8鈥?2 (1973)
  15.Hobby, D., McKenzie, R.: The structure of finite algebras, Contemporary Mathematics vol. 76. American Mathematical Society, Providence (1988). Revised edition (1996)
  16.J贸nsson, B.: Algebras whose congruence lattices are distributive. Math. Scand. 21 (1967), 110鈥?21 (1968)
  17.Kearnes, K.A., Kiss, E.W.: The shape of congruence lattices. Mem. Amer. Math. Soc. 222 (1046) (2013)
  18.Kearnes K., Markovi膰 P., McKenzie R.: Optimal strong Mal鈥檆ev conditions for omitting type 1 in locally finite varieties. Algebra Universalis 72, 91鈥?00 (2014)View Article MATH MathSciNet
  19.Kearnes K.A., Szendrei 脕.: Clones of algebras with parallelogram terms. Internat. J. Algebra Comput. 22(1), 1250005 (2012)View Article MathSciNet
  20.Mal鈥瞔ev A.I.: On the general theory of algebraic systems. Mat. Sb. N.S. 35(77), 3鈥?0 (1954)MathSciNet
  21.Mar贸ti M., McKenzie R.: Existence theorems for weakly symmetric operations. Algebra Universalis 59, 463鈥?89 (2008)View Article MATH MathSciNet
  22.McKenzie, R.N., McNulty, G.F., Taylor, W.F.: Algebras, lattices, varieties. Vol. I. The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey (1987)
  23.Ne拧et艡il, J., Siggers, M.: Combinatorial proof that subprojective constraint satisfaction problems are NP-complete. In: Mathematical foundations of computer science 2007, Lecture Notes in Comput. Sci., vol. 4708, pp. 159鈥?70. Springer, Berlin (2007)
  24.Siggers M.H.: A strong Mal鈥檆ev condition for locally finite varieties omitting the unary type. Algebra Universalis 64, 15鈥?0 (2010)View Article MATH MathSciNet
  
• 作者单位：Marcin Kozik (1)
  Andrei Krokhin (2)
  Matt Valeriote (3)
  Ross Willard (4)
  
  1. Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Krak贸w, Poland
  2. School of Engineering and Computing Sciences, Durham University, Durham, UK
  3. Department of Mathematics & Statistics, McMaster University, Hamilton, Ontario, Canada
  4. Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Algebra
  
• 出版者：Birkh盲user Basel
• ISSN：1420-8911

文摘

Tame congruence theory identifies six Maltsev conditions associated with locally finite varieties omitting certain types of local behaviour. Extending a result of Siggers, we show that of these six Maltsev conditions only two of them are equivalent to strong Maltsev conditions for locally finite varieties. Besides omitting the unary type, the only other of these conditions that is strong is that of omitting the unary and affine types. We also provide novel presentations of some of the above Maltsev conditions.