Koshkin, Sergiy
(2024)
Functional completeness and primitive positive decomposition of relations on finite domains.
Logic Journal of the IGPL.
ISSN 1367-0751
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.
Item Type: |
Published Article or Volume
|
Creators: |
|
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 |