Oscillating Behavior of Logic Programs

Katsumi Inoue and Chiaki Sakama

Correct Reasoning: Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Lecture Notes in Computer Science 7265, Springer-Verlag, pages 345-362, 2012.

Abstract

We examine oscillation behavior of normal logic programs. Both the Gelfond-Lifschitz operator and the Tp operator are used to update Herbrand interpretations, and any interpretation finally reaches in an oscillator. It has been shown that the supported model semantics of normal logic programs can characterize point attractors of Boolean networks. We here newly define supported classes of normal logic programs to investigate periodic oscillation induced by the Tp operator, and apply them to characterize cycle attractors of Boolean networks. We also relate stable classes and supported classes of normal logic programs.

Full Paper (PDF 211K)