ArticleOriginal scientific text

Title

Clausal relations and C-clones

Authors 1

Affiliations

  1. Institut für Algebra, TU Dresden, Germany

Abstract

We introduce a special set of relations called clausal relations. We study a Galois connection Pol-CInv between the set of all finitary operations on a finite set D and the set of clausal relations, which is a restricted version of the Galois connection Pol-Inv. We define C-clones as the Galois closed sets of operations with respect to Pol-CInv and describe the lattice of all C-clones for the Boolean case D = {0,1}. Finally we prove certain results about C-clones over a larger set.

Keywords

clone, Galois connection, clausal relation, C-clone

Bibliography

  1. N. Creignou, M. Hermann, A. Krokhin and G. Salzer, Complexity of clausal constraints over chains, Theory Comput. Syst., Theory of Computing Systems 42 (2) (2008), 239-255. doi: 10.1007/s00224-007-9003-z
  2. E.L. Post, The Two- Valued Iterative Systems of Mathematical Logic, Annals of Mathematics Studies, no. 5, Princeton University Press, Princeton, N. J. (1941), pages viii+122.
  3. R. Pöschel and L.A. Kalužnin, Funktionen- und Relationenalgebren, Mathematische Monographien [Mathematical Monographs], 15, VEB Deutscher Verlag der Wissenschaften, Berlin (1979), pages 259
Pages:
147-171
Main language of publication
English
Received
2009-04-22
Accepted
2009-12-16
Published
2010
Exact and natural sciences