The work described in this dissertation is mainly a study of some ordinal-theoretic properties of logic programs that are related to the downward powers of their immediate-consequence functions. The downward powers for any program give rise to an interesting non-increasing sequence of interpretations, whose point of convergence is called the downward closure ordinal of that program. The last appearance of ground atoms that get eliminated somewhere in this sequence is called their downward order.
While it is well-known that there is no general procedure that can determine downward orders of atoms in any program, we present some rules for constructing such a procedure for a restricted class of programs.
Another existing result is that for every ordinal up to and including the least non-recursive ordinal [special characters omitted] there is a logic program having that ordinal as its downward closure ordinal. However, the literature contains only a few examples of programs, constructed in an ad hoc manner, with downward closure ordinal greater than the least transfinite ordinal (ω). We contribute to bridging this wide gap between the abstract and concrete knowledge 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 and a convenient notation system for ordinals involving ground terms as bases, we construct a family [special characters omitted] of logic programs where [special characters omitted] is the least fixpoint of the function λβ[ωβ] and any member Pα of the family has downward closure ordinal ω + α.
We also present an organization of a general transformation system, in which the objective is to search for transformations on syntax objects that satisfy pre-established semantic constraints. As desired transformations are not always guaranteed to exist, we present necessary and sufficient conditions for their existence. In this framework, we proceed to give transformations on logic programs for the successor and addition operations on their downward closure ordinals. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/9476 |
| Date | 19 June 2018 |
| Creators | Bagai, Rajiv |
| Contributors | Van Emden, M. H. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0021 seconds