OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT Journal Articles uri icon

  •  
  • Overview
  •  
  • Research
  •  
  • Identity
  •  
  • Additional Document Info
  •  
  • View All
  •  

abstract

  • We say that a finite algebra � = 〈A; F〉 has the ability to count if there are subalgebras C of �3 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) �2 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.

publication date

  • August 2009