Tarski clones of operations on binary relations and their characterization
by
Reinhard Pöschel
Technische Universität Dresden, Institut für Algebra
Coauthors: Dragan Masulovic (University Novi Sad)

In the talk we give a characterization of the following three clones of operations on binary relations: the clone of primitive-positive Tarski operations, the clone of positive Tarski operations and the clone of all Tarski operations (or the classical clone). Operations from each of the three clones can be represented by special first-order formulas; to each such formula we assign a labelled multigraph and show that an operation belongs to the respective clone if and only if the suitably transformed graph of its formula does not contain a subgraph homeomorphic to K₄. Finally, we address a problem of A. Tarski to characterize closed first-order formulas that can be in a suitable way represented by an identity in the language of relation algebras.

Date received: January 10, 2003