The finite representation property for composition, intersection, domain and range
McLean, B., Szabolcs Mikulás · BIROn (Birkbeck, University of London) · 2016
We prove that the nite representation property holds for rep- resentation by partial functions for the signature consisting of composition, intersection, domain and range and for any expansion of this signature by the antidomain, xset, preferential union, maximum iterate and opposite opera- tions. The proof shows that, for all these signatures, the size of base required is bounded by a double-exponential function of the size of the algebra. This establishes that representability of nite algebras is decidable for all these signatures. We also give an example of a signature for which the nite repre- sentation property fails to hold for representation by partial functions.