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)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 537 | Parallel Evaluation of Recursive Rule Queries | 1986 | PODS | 0.0002068591 |
| 1,185 | Data Independent Recursion in Deductive Databases | 1986 | PODS | 0.00013445831 |
| 1,991 | Decidability and Undecidability Results for Boundedness of Linear Recursive Queries | 1988 | PODS | 9.84713e-05 |
| 4,631 | Tools for Datalog Boundedness | 1991 | PODS | 6.0347472e-05 |
| 6,143 | Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP | 2013 | PODS | 5.1889914e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,794 | Complexity of Nonrecursive Logic Programs with Complex Values | 1998 | PODS | 4.9244886e-05 |
| 4,370 | Distributed Processing Of Logic Programs | 1988 | SIGMOD | 6.2486359e-05 |
| 6,236 | Inherent Complexity of Recursive Queries (Extended Abstract) | 1999 | PODS | 5.1436959e-05 |
| 7,018 | Hard problems for simple logic programs | 1990 | SIGMOD | 4.8602644e-05 |
| 4,136 | Safety of Datalog Queries over Infinite Databases | 1989 | PODS | 6.4188795e-05 |
| 7,598 | Polynomial-time program transformations in deductive databases | 1990 | PODS | 4.7004867e-05 |
| 6,848 | Flag & Check: Data Access with Monadically Defined Queries | 2013 | PODS | 4.9089877e-05 |
| 7,591 | On the First-Order Expressibility of Recursive Queries | 1989 | PODS | 4.702934e-05 |
| 4,631 | Tools for Datalog Boundedness | 1991 | PODS | 6.0347472e-05 |
| 13,585 | Monadic Datalog over Finite Structures with Bounded Treewidth | 2007 | PODS | - |