Koshkin, Sergiy (2024) Functional completeness and primitive positive decomposition of relations on finite domains. Logic Journal of the IGPL. ISSN 1367-0751

Preview

Text Functional Reduction.pdf Download (324kB) | Preview

Abstract

We give a new and elementary construction of primitive positive decomposition of higher arity relations into binary relations on finite domains. Such decompositions come up in applications to constraint satisfaction problems, clone theory and relational databases. The construction exploits functional completeness of 2-input functions in many-valued logic by interpreting relations as graphs of partially defined multivalued `functions'. The `functions' are then composed from ordinary functions in the usual sense. The construction is computationally effective and relies on well-developed methods of functional decomposition, but reduces relations only to ternary relations. An additional construction then decomposes ternary into binary relations, also effectively, by converting certain disjunctions into existential quantifications. The result gives a uniform proof of Peirce's reduction thesis on finite domains, and shows that the graph of any Sheffer function composes all relations there.

---

Export/Citation:

EndNote | BibTeX | Dublin Core | ASCII/Text Citation (Chicago) | HTML Citation | OpenURL

Social Networking:

Share |

---

Item Type:	Published Article or Volume
Creators:	Creators Email ORCID Koshkin, Sergiy 0000-0001-8264-3701
Keywords:	relational operations, primitive positive formula, coclone, constraint satisfaction problem, irreducible relation, many-valued logic, functional completeness, Sheffer functions, Post algebra, relative product, hypostatic abstraction, Peirce's reduction thesis
Subjects:	Specific Sciences > Computation/Information > Classical Specific Sciences > Mathematics > Logic
Depositing User:	Dr. Sergiy Koshkin
Date Deposited:	11 Jun 2024 17:18
Last Modified:	11 Jun 2024 17:18
Item ID:	23545
Journal or Publication Title:	Logic Journal of the IGPL
Publisher:	Oxford University Press
Official URL:	https://academic.oup.com/jigpal/advance-article-ab...
DOI or Unique Handle:	https://doi.org/10.1093/jigpal/jzae077
Subjects:	Specific Sciences > Computation/Information > Classical Specific Sciences > Mathematics > Logic
Date:	1 June 2024
ISSN:	1367-0751
URI:	https://philsci-archive.pitt.edu/id/eprint/23545

Monthly Views for the past 3 years

Monthly Downloads for the past 3 years

Plum Analytics

Altmetric.com

Actions (login required)

View Item