DBScholar

Back to papers

Monadic Datalog over Finite Structures with Bounded Treewidth

Summary: Compile MSO-definable properties on bounded-treewidth structures into monadic datalog over the structure+tree decomposition, avoiding finite tree automaton state explosion. Prove linear-time evaluation in both program and data size for this datalog fragment and validate with a new PRIMALITY algorithm and prototype experiments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1425
Venue
PODS
Year
2007
Pagerank
-
Overall Rank
13,785 | 5.43%
DOI
10.1145/1265530.1265554

Incoming Non-self Citations Over Time

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

Authors

BibTeX Citation

@inproceedings{gottlob_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Monadic Datalog over Finite Structures with Bounded Treewidth}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265554},
        doi = {10.1145/1265530.1265554},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Pichler, Reinhard and Wei, Fang},
        year = {2007}
}

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 2 of 2 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,180 Monadic Datalog and the Expressive Power of Languages for Web Information Extraction 2002 PODS 9.0110009e-05
9,864 Tractable Database Design through Bounded Treewidth 2006 PODS 5.2045536e-05
Previous Page 1 / 1 Next

Semantically Similar Papers