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: 902
Venue: PODS
Year: 1990
Pagerank: 6.4877275e-05
Overall Rank: 4,831 | 66.86%
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,560	Minimum and Maximum Predicates in Logic Programming	1991	PODS	7.3094581e-05
4,290	Greedy by Choice	1992	PODS	6.7791707e-05
4,943	Datalog Unchained	2021	PODS	6.4332239e-05
5,964	Negation and Minimality in Non-Horn Databases	1993	PODS	6.0262735e-05
8,083	The Valid Model Semantics for Logic Programs	1992	PODS	5.4911506e-05
8,773	Semi-determinism (extended abstract)	1992	PODS	5.3766157e-05
9,326	Extending Logic Programming	1990	SIGMOD	5.289545e-05
13,105	A Non-deterministic Deductive Database Language	1991	SIGMOD	5.093636e-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
989	Why Not Negation By Fixpoint?	1988	PODS	0.00012804792
1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS	0.0001126031
1,419	Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model	1989	PODS	0.00010830412
1,522	Unfounded Sets and Well-Founded Semantics for General Logic Programs	1988	PODS	0.00010502706
2,028	A Procedural Semantics for Well Founded Negation in Logic Programs	1989	PODS	9.285972e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,026	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS
2	5,210	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS
3	5,964	Negation and Minimality in Non-Horn Databases	1993	PODS
4	5,735	Tie-Breaking Semantics and Structural Totality (Extended Abstract)	1992	PODS
5	1,419	Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model	1989	PODS
6	3,712	Non-Deterministic Languages to Express Deterministic Transformations	1990	PODS
7	1,522	Unfounded Sets and Well-Founded Semantics for General Logic Programs	1988	PODS
8	11,968	Stable Model Semantics for Tuple-Generating Dependencies Revisited	2017	PODS
9	8,083	The Valid Model Semantics for Logic Programs	1992	PODS
10	1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS