Sixty Years of Stable Models

Twenty years ago Michael Gelfond and Vladimir Lifschitz published their celebrated paper on the stable model semantics of logic programs. Today, having built on and enlarged those key ideas of twenty years ago, answer set programming (ASP) has emerged as a flourishing paradigm of declarative programming, rich in theoretical advances and maturing applications. This is one aspect of the legacy of stable models, and a very important one. Another aspect, equally important, but somewhat farther from the limelight today, resides in the ability of stable models to provide us with a valuable method of reasoning - to give it a name let us call it

stable reasoning

. In the full version of this essay I examine some of the foundational concepts underlying the approach of stable models. I try to answer the question: “What is a stable model?” by searching for a purely logical grasp of the stability concept. In so doing, I shall discuss some concepts and results in logic from around 60 years ago. In particular, I look at questions such as:

How does a notion of stability presented in a work on intuitionistic mathematics in 1947 relate to the Gelfond-Lifschtiz concept of 1988?

How does the notion of constructible falsity published in 1949 help to explain certain properties of negation arising in the language of ASP?

Why is a seminal paper by McKinsey and Tarski, published in 1948, important for understanding the relations between answer sets and epistemic logic?