Functional completeness and primitive positive decomposition of relations on finite domains
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.19492
curl -X POST /api/v1/records/arxiv/2606.19492/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.19492/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'