Stable Models for Stubborn Sets

Reference:

Kimmo Varpaaniemi. Stable models for stubborn sets. In Hans-Dieter Burkhard, Ludwik Czaja, Hung Son Nguyen, and Peter H. Starke, editors, Concurrency, Specification and Programming: Proceedings of the CS&P'99 Workshop, Warsaw, Poland, 28–30 September 1999, pages 263–274. Zakład Graficzny UW, zam. 482/99, Warsaw, Poland, 1999.

Abstract:

The stubborn set method is one of the methods that try to relieve the state space explosion problem that occurs in state space generation. Spending some time in looking for ``good'' stubborn sets can pay off in the total time spent in generating a reduced state space. This paper shows how the method can exploit tools that solve certain problems of logic programs. The restriction of a definition of stubbornness to a given state can be translated into a variable-free logic program. When a stubborn set satisfying additional constraints is wanted, the additional constraints should be translated, too. It is easy to make the translation in such a way that each acceptable stubborn set of the state is represented by at least one stable model of the program, each stable model of the program represents at least one acceptable stubborn set of the state, and for each pair in the representation relation, the number of certain atoms in the stable model is equal to the number of enabled transitions of the represented stubborn set. So, in order to find a stubborn set which is good w.r.t. the number of enabled transitions, it suffices to find a stable model which is good w.r.t. the number of certain atoms.

Keywords:

reachability analysis, reduced state space generation, stubborn sets, variable-free logic programs, stable models

Suggested BibTeX entry:

@inproceedings{VarpaaniemiKimmo-Vrp99,
    author = {Kimmo Varpaaniemi},
    booktitle = {{C}oncurrency, Specification and Programming: Proceedings of the {C}{S}\&{P}'99 Workshop, {W}arsaw, {P}oland, 28--30 {S}eptember 1999},
    editor = {Hans-Dieter Burkhard and Ludwik Czaja and Hung Son Nguyen and Peter H. Starke},
    pages = {263--274},
    publisher = {Zak{\l}ad Graficzny UW, zam. 482/99, Warsaw, Poland},
    title = {{S}table Models for Stubborn Sets},
    year = {1999},
}