Download PDF - Clausal relations and C-clones
ArticleOriginal scientific text
Title
Clausal relations and C-clones
Authors 1
Affiliations
- 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
- 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
- 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.
- 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