Termination Detection in Logic Programs using Argument Sizes* (Extended Abstract)

Summary: Automated termination test that models predicate argument sizes as vectors in R^n and finds a nonnegative linear combination guaranteed to decrease in top-down recursion. Uses LP duality to handle nonlinear/mutual recursion; only a sufficient criterion and needs syntactic rewrites. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h44a57962342a6b35
Venue: PODS
Year: 1991
Pagerank: 5.4126988e-05
Overall Rank: 7,984 | 46.33%
DOI: 10.1145/113413.113433

Incoming Non-self Citations Over Time

Authors

1. Kirack Sohn (University of California Santa Cruz)
2. Allen Van Gelder (University of California Santa Cruz)

BibTeX Citation

@inproceedings{sohn_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{Termination Detection in Logic Programs using Argument Sizes* (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/113413.113433},
        doi = {10.1145/113413.113433},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sohn, Kirack and Van Gelder, Allen},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,904	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	6.9336057e-05
13,308	Constraints among Argument Sizes in Logic Programs (Extended Abstract)	1994	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,152	Querying Constraints	1990	PODS	8.951621e-05
2,629	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	8.2045999e-05
3,417	Deriving Constraints Among Argument Sizes in Logic Programs (Extended Abstract)	1990	PODS	7.3218419e-05
3,904	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	6.9336057e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,798	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS
2	7,696	Hard problems for simple logic programs	1990	SIGMOD
3	2,062	A Decidable Class of Bounded Recursions	1987	PODS
4	4,712	Tools for Datalog Boundedness	1991	PODS
5	8,053	Polynomial-time program transformations in deductive databases	1990	PODS
6	7,599	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS
7	5,413	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
8	3,417	Deriving Constraints Among Argument Sizes in Logic Programs (Extended Abstract)	1990	PODS
9	13,308	Constraints among Argument Sizes in Logic Programs (Extended Abstract)	1994	PODS
10	3,904	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS