Deciding Boundedness of Monadic Sirups

Summary: Shows that deciding boundedness (FO-rewritability) for monadic single-rule datalog programs (sirups) is 2ExpTime-hard, matching the long-known 2ExpTime upper bound and settling a long-standing open problem. Also proves 2ExpTime-hardness for FO-rewritability of disjunctive sirups with dag-shaped CQs and makes substantial progress toward a complete FO/L-hardness dichotomy for ditree-shaped queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1859
Venue: PODS
Year: 2021
Pagerank: 5.093636e-05
Overall Rank: 11,639 | 20.15%
DOI: 10.1145/3452021.3458332

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Stanislav Kikot (Institute for Information Transmission Problems)
2. Agi Kurucz (King's College London)
3. Vladimir V. Podolskii (National Research University Higher School of Economics)
4. Michael Zakharyaschev (Birkbeck, University of London; National Research University Higher School of Economics)

BibTeX Citation

@inproceedings{kikot_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Deciding Boundedness of Monadic Sirups}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458332},
        doi = {10.1145/3452021.3458332},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kikot, Stanislav and Kurucz, Agi and Podolskii, Vladimir V. and Zakharyaschev, Michael},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
1,173	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011822695
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
4,615	Tools for Datalog Boundedness	1991	PODS	6.6050069e-05
5,347	Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP	2013	PODS	6.2571376e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,661	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS
2	4,121	Distributed Processing Of Logic Programs	1988	SIGMOD
3	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
4	7,549	Hard problems for simple logic programs	1990	SIGMOD
5	6,077	Safety of Datalog Queries over Infinite Databases	1989	PODS
6	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
7	7,411	Flag & Check: Data Access with Monadically Defined Queries	2013	PODS
8	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
9	4,615	Tools for Datalog Boundedness	1991	PODS
10	13,785	Monadic Datalog over Finite Structures with Bounded Treewidth	2007	PODS