C.F.M. Vermeulen: More computation power for a denotational semantics for first order logic  

To gain computational realism a decrease in expressivity compared to first order logic is inevitable. In Apt's proposal the expressivity was compared with logic programming with both positive and negative results. Here we consider three ways of improving the situation: replacing the conjunctionassequentialcomposition in the original proposal by a symmetric interpretation of conjunction; extending the framework with the option of recursive definitions by Clark completions; replacing the interpretation of disjunctionaschoice by an interpretation which is in the style of `backtracking': only produce an error message if all options lead to error. For each improvement we obtain a soundness result. The three improvements are developed independently in a way that makes sure that also their combination preserves soundness. The combination gives a considerable improvement of the expressivity of the denotational semantics that Apt proposed, both in the comparison with first order logic and in the comparison with logic programming.
