Oscillating Behavior of Logic Programs
Katsumi Inoue and Chiaki Sakama
Essays on Logic-Based AI in Honour of Vladimir Lifschitz,
Lecture Notes in Computer Science 7265, Springer-Verlag, pages 345-362, 2012.
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)