2003/07/30 by C. F. M. Vermeulen, Vermeulen, C. F. M.
Computer Science · #D.1.6 #D.3.1 #F.3.2 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Semantic Web and Ontologies #cs.LO
paper · pdf · doi:10.48550/arxiv.cs/0307067
To appear in print shortly in the Progress in Computer Science Series of Novapublications
arxiv created 2003/07/30 · openalex publication_date 2003/07/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we adapt the definitions and results from Apt and Vermeulen on `First order logic as a constraint programming language' (in: Proceedings of LPAR2001, Baaz and Voronkov (eds.), Springer LNAI 2514) to include important ideas about search and choice into the system. We give motivating examples. Then we set up denotational semantics for first order logic as follows: the semantic universe includes states that consist of two components: a substitution, which can be seen as the computed answer; and a constraint satisfaction problem, which can be seen as the residue of the original problem, yet to be handled by constraint programming. The interaction between these components is regulated by an operator called: infer. In this paper we regard infer as an operator on sets of states to enable us to analyze ideas about search among states and choice between states. The precise adaptations of definitions and results are able to deal with the examples and we show that, given several reasonable conditions, the new definitions ensure soundness of the system with respect to the standard interpretation of first order logic. In this way the `reasonable conditions' can be read as conditions for sound search. We indicate briefly how to investigate efficiency of search in future research.