Narrow Results

Restriction semigroups model algebras of partial maps under composition and domain. Here we consider restriction semigroups for which the usual Boolean operations on domains are modeled. Such algebras are capable of modeling the usual modal operators considered in dynamic logic. Indeed adding a natural functional variant of union to the signature gives a deterministic version of the modal semirings of Möller and Struth, but also a monoidal version of the classical restriction categories of Cockett and Manes. Other operations modeled are intersection and (in the finite case) functional iteration. In each case, axiomatizations of the concrete functional examples are given, leading to algebraic models of partial maps incorporating all the domain-related and set-theoretic operations previously considered. Our algebras furnish natural algebraic semantics for the logics of deterministic computer programs, leading to new results for some variants of propositional dynamic logic.

Given tuples a₁, …, a_k and b in Aⁿ for some algebraic structure A, the subpower membership problem asks whether b is in the subalgebra of Aⁿ that is generated by a₁, …, a_k. For A a finite group, there is a folklore algorithm which decides this problem in time polynomial in n and k. We show that the subpower membership problem for any finite Mal'cev algebra is in NP and give a polynomial time algorithm for any finite Mal'cev algebra with finite signature and prime power size that has a nilpotent reduct. In particular, this yields a polynomial algorithm for finite rings, vector spaces, algebras over fields, Lie rings and for nilpotent loops of prime power order.

We prove that the finite representation property holds for representation by partial functions for the signature consisting of composition, intersection, domain and range and for any expansion of this signature by the antidomain, fixset, preferential union, maximum iterate and opposite operations. 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 finite algebras is decidable for all these signatures. We also give an example of a signature for which the finite representation property fails to hold for representation by partial functions.