No Access

OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT

Department of Mathematics and Statistics, Concordia University, 1455 de Maisonneuve West, Montréal, Qc, Canada, H3G 1M8, Canada

Search for more papers by this author

MATT VALERIOTE

Department of Mathematics and Statistics, McMaster University, 1280 Main Street, West Hamilton, Ontario, Canada L8S 4K1, Canada

Search for more papers by this author

, and

LÁSZLÓ ZÁDORI

Bolyai Intézet, Aradi vértanúk tere 1, H-6720, Szeged, Hungary

Search for more papers by this author

https://doi.org/10.1142/S021819670900524XCited by:10 (Source: Crossref)

Abstract

We say that a finite algebra 𝔸 = 〈A; F〉 has the ability to count if there are subalgebras C of 𝔸³ and Z of 𝔸 such that the structure 〈A; C, Z〉 has the ability to count in the sense of Feder and Vardi. We show that for a core relational structure A the following conditions are equivalent: (i) the variety generated by the algebra 𝔸 associated to A contains an algebra with the ability to count; (ii) 𝔸² has the ability to count; (iii) the variety generated by 𝔸 admits the unary or affine type. As a consequence, for CSP's of finite signature, the bounded width conjectures stated in Feder–Vardi [10], Larose–Zádori [17] and Bulatov [5] are identical.

Keywords:

AMSC: 68Q25, 08B05

References

F. Afrati, S. S. Cosmadakis and M. Yannakakis, On Datalog vs. polynomial time, Proc. 10th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (1991) pp. 13–25. Google Scholar
A. Atserias, A. Bulatov and A. Dawar, Affine systems of equations and counting infinitary logic, ICALP'074596, LNCS (2007) pp. 558–570. Google Scholar
L. Barto and M. Kozik, Constraint Satisfaction Problems of Bounded Width, manuscript, January 2009 . Google Scholar
J. D. Bermanet al., Discrete Math. 112(3), 1 (1993), DOI: 10.1016/0012-365X(93)90219-J. Crossref, Web of Science, Google Scholar
A. Bulatov, A graph of a relational structure and constraint satisfaction problems, LICS'04 (2004) pp. 448–457. Google Scholar
A. Bulatov, A. Krokhin and B. Larose, Complexity of Constraints, LNCS 5250 (2008) pp. 93–124. Crossref, Google Scholar
A. Bulatov and M. Valeriote, Complexity of Constraints, LNCS 5250 (2008) pp. 68–92. Crossref, Google Scholar
V. Dalmau, Logical Methods in Computer Science 1(1), (2005), DOI: 10.2168/LMCS-1(1:5)2005. Google Scholar
T. Feder and M. Y. Vardi, Monotone monadic SNP and constraint satisfaction, Proc. of the 25rd Annual ACM Symposium on Theory of Computing (STOC) (1993) pp. 612–622. Google Scholar
T. Feder and M. Y. Vardi, SIAM J. Comput. 28, 57 (1998), DOI: 10.1137/S0097539794266766. Crossref, Web of Science, Google Scholar
R. Freese and R. McKenzie , Commutator Theory for Congruence Modular Varieties , London Mathematical Society Lecture Note Series 125 ( Cambridge Universit Press , 1987 ) . Google Scholar
D. Hobby and R. McKenzie, Contemp. Math. (1988). Google Scholar
Ph. G. Kolaitis and M. Y. Vardi, J. Comput. System Sci. 51, 110 (1995), DOI: 10.1006/jcss.1995.1055. Crossref, Web of Science, Google Scholar
B. Larose and L. Haddad, Colourings of hypergraphs, permutation groups ans CSP's, Logic Colloquium '0427, Lect. Notes Log (2008) pp. 93–108. Google Scholar
B. Larose, C. Loten and C. Tardif, Logical Methods in Computer Science 3(4), (2007), DOI: 10.2168/LMCS-3(4:6)2007. Google Scholar
B. Larose and P. Tesson, Theoret. Comput. Sci. 410, 1629 (2009), DOI: 10.1016/j.tcs.2008.12.048. Crossref, Web of Science, Google Scholar
B. Larose and L. Zádori, Algebra Universalis 56(4), 439 (2007), DOI: 10.1007/s00012-007-2012-6. Crossref, Web of Science, Google Scholar
L. Libkin , Elements of Finite Model Theory ( Springer , 2004 ) . Crossref, Google Scholar
A. A. Razborov, Math. Notes 37(6), 485 (1985). Crossref, Web of Science, Google Scholar
Á. Szendrei, Research and Exposition in Mathematics (Heldermann Verlag, 1992) pp. 209–239. Google Scholar
Á. Szendrei, J. Austral. Math. Soc. Ser. A 48(3), 434 (1990), DOI: 10.1017/S1446788700029979. Crossref, Google Scholar
Á. Szendrei , Seminaires de Mathematiques Superieures 99 ( University of Montreal , 1986 ) . Google Scholar
M. Valeriote , Canadian J. Math. 18 . Web of Science, Google Scholar