Syntactically Recognizable Modularly Stratified Programs.
David B. Kemp, Kotagiri Ramamohanarao · 1994
We present an efficient evaluation technique for modularly stratified programs for which the local strata level mappings are known at compile time. We present an important subclass of these programs (called EMS-programs) in which one can easily express problems such as shortest distance, company ownership, bill of materials, preferential vote counting, and matrix diagonalization. Programs written in this style are easier to understand and can be efficiently computed. Another virtue of these programs is that their modular-stratification properties are independent of the extensional database. We also present compiler optimizations for EMS-programs. y Revised December 1 Introduction Programs that contain recursion through negation or aggregation suffer from two major problems. The first is that such programs are often difficult to understand. This is reflected in the fact that there have been several complicated and conflicting proposals for the semantics of aggregation and negation. T...