Preservation theorems for Tarski's relation algebra
Open Access
- 4 September 2024
- journal article
- research article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is (3)
Abstract
We investigate a number of semantically defined fragments of Tarski's algebra of binary relations, including the function-preserving fragment. We address the question whether they are generated by a finite set of operations. We obtain several positive and negative results along these lines. Specifically, the homomorphism-safe fragment is finitely generated (both over finite and over arbitrary structures). The function-preserving fragment is not finitely generated (and, in fact, not expressible by any finite set of guarded second-order definable function-preserving operations). Similarly, the total-function-preserving fragment is not finitely generated (and, in fact, not expressible by any finite set of guarded second-order definable total-function-preserving operations). In contrast, the forward-looking function-preserving fragment is finitely generated by composition, intersection, antidomain, and preferential union. Similarly, the forward-and-backward-looking injective-function-preserving fragment is finitely generated by composition, intersection, antidomain, inverse, and an `injective union' operation.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- The power of Tarski's relation algebra on treesJournal of Logical and Algebraic Methods in Programming, 2022
- An Algebra of Modular Systems: Static and Dynamic PerspectivesLecture Notes in Computer Science, 2019
- How Many Variables are Needed to Express an Existential Positive Query?Theory of Computing Systems, 2018
- The algebra of functions with antidomain and rangeJournal of Pure and Applied Algebra, 2016
- Relative expressive power of navigational querying on graphsInformation Sciences, 2015
- MODAL RESTRICTION SEMIGROUPS: TOWARDS AN ALGEBRA OF FUNCTIONSInternational Journal of Algebra and Computation, 2011
- A NONCOMMUTATIVE GENERALIZATION OF STONE DUALITYJournal of the Australian Mathematical Society, 2010
- Homomorphism preservation theoremsJournal of the ACM, 2008
- A New Modal Lindström TheoremLogica Universalis, 2007
- Algorithmic uses of the Feferman–Vaught TheoremAnnals of Pure and Applied Logic, 2004