𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Floyd–Warshall algorithm for logic programs

✍ Scribed by Christos Papadimitriou; Martha Sideri

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
114 KB
Volume
41
Category
Article
ISSN
0743-1066

No coin nor oath required. For personal study only.

✦ Synopsis

We explore the possibility of evaluating single-rule Datalog programs eciently and with logarithmic work space by a natural extension of the Floyd±Warshall algorithm for transitive closure. We characterize exactly the single rule chain programs that can be so evaluated ± they are rather modest generalizations of the transitive closure. The proof relies on an interesting language-theoretic concept, total ambiguity. Extensions to more general classes of programs, and more general algorithms, are discussed.

📜 SIMILAR VOLUMES

On the equivalence of semantics for norm
On the equivalence of semantics for normal logic programs
✍ Jia-Huai You; Li Yan Yuan 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 699 KB

Despite the frequent comment that there is no general agreement on the semantics of logic programs, this paper shows that a number of independently proposed extensions to the stable model semantics coincide: the regular model semantics proposed by You and Yuan, the partial stable model semantics by

A note on the stable model semantics for
A note on the stable model semantics for logic programs
✍ Michael Kaminski 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 900 KB

The stable model semantics for logic programs is extended from ground literals onto open literals by augmenting the program language with an infinite set of new constants. This, in turn, leads to a natural translation of logic programs into open default theories. @

On the Decidability of Propositional Alg
On the Decidability of Propositional Algorithmic Logic
✍ Bogdan S. Chlebus 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 802 KB

ON THE DECIDABILITY OF PROPOSITIONAL ALGORITHMIC LOGIC by BOGDAN S. CHLEBIJS in Warsaw (Po1and)l) 0. Introduction Let PAL be a n abbreviation for propositional algorithmic logic. The investigation of PAL is a continuation of earlier works on algorithmic logic (GRABOWSKI [3], KRECZMAR [5], SALWICKI [