Fundamenta Informaticae - Volume 13, issue 1

Article Type: Other

DOI: 10.3233/FI-1990-13101

Citation: Fundamenta Informaticae, vol. 13, no. 1, pp. I-VIII, 1990

Article Type: Editorial

DOI: 10.3233/FI-1990-13102

Citation: Fundamenta Informaticae, vol. 13, no. 1, pp. v-ix, 1990

Authors: Apt, Krzysztof R. | Blair, Howard A.

Article Type: Research Article

Abstract: We study here the recursion theoretic complexity of the perfect (Herbrand) models of stratified logic programs. We show that these models lie arbitrarily high in the arithmetic hierarchy. As a byproduct we obtain a similar characterization of the recursion theoretic complexity of the set of consequences in a number of formalisms for non-monotonic reasoning. We show that under some circumstances this complexity can be brought down to recursive enumerability.

DOI: 10.3233/FI-1990-13103

Citation: Fundamenta Informaticae, vol. 13, no. 1, pp. 1-17, 1990

Authors: Fitting, Melvin | Ben-Jacob, Marion

Article Type: Research Article

Abstract: We investigate the relationship between three-valued Kripke/Kleene semantics and stratified semantics for stratifiable logic programs. We first show these are compatible, in the sense that if the three-valued semantics assigns a classical truth value, the stratified approach will assign the same value. Next, the familiar fixed point semantics for pure Horn clause programs gives both smallest and biggest fixed points fundamental roles. We show how to extend this idea to the family of stratifiable logic programs, producing a semantics we call weak stratified. Finally, we show weak stratified semantics coincides exactly with the three-valued approach on stratifiable programs, though the …three-valued version is generally applicable, and does not require stratification assumptions. Show more

DOI: 10.3233/FI-1990-13104

Citation: Fundamenta Informaticae, vol. 13, no. 1, pp. 19-33, 1990

Authors: Kunen, Kenneth

Article Type: Research Article

Abstract: We show how Clark’s Completed Database (CDB) can be extended to include a number of Prolog constructs usually considered to be outside of pure logic, while still maintaining the known partial completeness results for SLDNF derivations. We also prove that in the semantics provided by the CDB and SLDNF, there is no definition of transitive closure which is strict and does not use function symbols.

DOI: 10.3233/FI-1990-13105

Citation: Fundamenta Informaticae, vol. 13, no. 1, pp. 35-49, 1990

Authors: Przymusinska, Halina | Przymusinski, Teodor C.

Article Type: Research Article

DOI: 10.3233/FI-1990-13106

Citation: Fundamenta Informaticae, vol. 13, no. 1, pp. 51-65, 1990

Authors: Bagai, Rajiv | Bezem, Marc | van Emden, M.H.

Article Type: Research Article

Abstract: Blair has shown that for every ordinal up to and including the least non-recursive ordinal there exists a logic program having that ordinal as downward closure ordinal. However, given such an ordinal and Blair’s proof, it is not straightforward to find a corresponding logic program. In fact, in the literature only a few isolated, ad hoc , examples of logic programs with downward closure ordinal greater than w can be found. We contribute to bridging the gap between what is known abstractly and what is known concretely by showing the connection between some of the existing examples and the …well-known concept of the order of a vertex in a graph. Using this connection as a basis, we construct a family { P α } α < ϵ 0 of logic programs where any member P α has downward closure ordinal ω + α . Show more

DOI: 10.3233/FI-1990-13107

Citation: Fundamenta Informaticae, vol. 13, no. 1, pp. 67-83, 1990