Stable Models and Non-Determinism in Logic Programs with Negation

Summary: Unifies negation and nondeterminism via stable-model semantics, defines partial/strongly-founded/deterministic/stable models, and proves max-deterministic ⊆ ⋂stable and well-founded ⊆ max-deterministic. Subsumes LDL's nondeterministic choice and gives a backtracking-fixpoint to construct total stable models. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h3e02e31395f93afc
Venue: PODS
Year: 1990
Pagerank: 6.3391787e-05
Overall Rank: 4,952 | 66.72%
DOI: 10.1145/298514.298572

Incoming Non-self Citations Over Time

Authors

1. Domenico Saccà (University of Calabria)
2. Carlo Zaniolo (Microelectronics And Technology Computer Corporation)

BibTeX Citation

@inproceedings{sacca_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{Stable Models and Non-Determinism in Logic Programs with Negation}},
        url = {https://dl.acm.org/doi/10.1145/298514.298572},
        doi = {10.1145/298514.298572},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Saccà, Domenico and Zaniolo, Carlo},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,624	Minimum and Maximum Predicates in Logic Programming	1991	PODS	7.1502242e-05
4,373	Greedy by Choice	1992	PODS	6.6283681e-05
5,070	Datalog Unchained	2021	PODS	6.2869206e-05
6,089	Negation and Minimality in Non-Horn Databases	1993	PODS	5.8882714e-05
8,259	The Valid Model Semantics for Logic Programs	1992	PODS	5.365458e-05
8,943	Semi-determinism (extended abstract)	1992	PODS	5.2534908e-05
9,516	Extending Logic Programming	1990	SIGMOD	5.168414e-05
13,401	A Non-deterministic Deductive Database Language	1991	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,012	Why Not Negation By Fixpoint?	1988	PODS	0.00012514931
1,326	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS	0.00011004102
1,459	Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model	1989	PODS	0.00010582864
1,556	Unfounded Sets and Well-Founded Semantics for General Logic Programs	1988	PODS	0.00010262577
2,079	A Procedural Semantics for Well Founded Negation in Logic Programs	1989	PODS	9.0743477e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,049	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS
2	5,341	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS
3	6,089	Negation and Minimality in Non-Horn Databases	1993	PODS
4	5,863	Tie-Breaking Semantics and Structural Totality (Extended Abstract)	1992	PODS
5	1,459	Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model	1989	PODS
6	3,799	Non-Deterministic Languages to Express Deterministic Transformations	1990	PODS
7	1,556	Unfounded Sets and Well-Founded Semantics for General Logic Programs	1988	PODS
8	12,272	Stable Model Semantics for Tuple-Generating Dependencies Revisited	2017	PODS
9	8,259	The Valid Model Semantics for Logic Programs	1992	PODS
10	1,326	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS