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: 938
Venue: PODS
Year: 1991
Pagerank: 5.5368828e-05
Overall Rank: 7,824 | 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,824	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0919497e-05
13,018	Constraints among Argument Sizes in Logic Programs (Extended Abstract)	1994	PODS	5.093636e-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,111	Querying Constraints	1990	PODS	9.1515689e-05
2,579	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	8.3906191e-05
3,360	Deriving Constraints Among Argument Sizes in Logic Programs (Extended Abstract)	1990	PODS	7.4890377e-05
3,824	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0919497e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,661	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS
2	7,549	Hard problems for simple logic programs	1990	SIGMOD
3	2,015	A Decidable Class of Bounded Recursions	1987	PODS
4	4,615	Tools for Datalog Boundedness	1991	PODS
5	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
6	7,454	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS
7	5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
8	3,360	Deriving Constraints Among Argument Sizes in Logic Programs (Extended Abstract)	1990	PODS
9	13,018	Constraints among Argument Sizes in Logic Programs (Extended Abstract)	1994	PODS
10	3,824	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS