The classical decision problem and partial functions |
| |
Authors: | Motti Abramsky |
| |
Institution: | (1) Department of Mathematics, University of the Negev, Beer-Sheva, Israel |
| |
Abstract: | We consider the decision problem for sets of sentences of first-order logic when instead of interpreting function symbols as total functions over the universe of a model (henceforth referred to as the usual interpretation) we interpret them as partial functions.We consider only standard classes, which are certain sets of prenex sentences specified by restrictions on the prefix and on the numbers ofk-place predicate and function symbols for eachk1. Standard classes are introduced in 1] and it is proved there that the decision problem for any set of prenex sentences specified by such restrictions reduces to that for the standard classes.We solve the decision problem completely for standard classes with at least one function symbol and both with and without equality.This problem was suggested to me by my supervisor, Professor Yuri Gurevich who was confident that the results would be very similar to those for the usual interpretation and could be achieved by similar techniques. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|