Title: | Efficient counting with bounded treewidth using datalog | Language: | English | Authors: | Rümmele, Stefan | Qualification level: | Diploma | Keywords: | Abzählkomplexität; Parametrisierte Komplexität; Baumbreite; Datalog Counting complexity; Parameterized complexity; Treewidth; Datalog |
Advisor: | Pichler, Reinhard | Assisting Advisor: | Woltran, Stefan | Issue Date: | 2008 | Number of Pages: | 76 | Qualification level: | Diploma | Abstract: | Bounded treewidth has proven to be a key concept in identifying tractable fragments of inherently intractable problems. An important result in this context is Courcelle's Theorem, stating that any property of finite structures definable in monadic second-order logic (MSO), becomes tractable if the treewidth of the structure is bounded by a constant. An extension of this result to counting problems was done by Arnborg et al. But both proofs did not yield an implementable algorithm. Recently Gottlob et al.\ presented a new approach using monadic datalog to close this gap for decision problems. The goal of this work is to extend this method in order to handle counting problems as well. We show that the monadic datalog approach indeed is applicable for all MSO definable counting problems. Furthermore we propose concrete algorithms with fixed-parameter linear running time for the problems #SAT, #CIRCUMSCRIPTION and #HORN-ABDUCTION. |
URI: | https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-22267 http://hdl.handle.net/20.500.12708/14651 |
Library ID: | AC05039694 | Organisation: | E184 - Institut für Informationssysteme | Publication Type: | Thesis Hochschulschrift |
Appears in Collections: | Thesis |
Files in this item:
File | Description | Size | Format | |
---|---|---|---|---|
Efficient counting with bounded treewidth using datalog.pdf | 601.17 kB | Adobe PDF | ![]() View/Open |
Page view(s)
10
checked on Feb 18, 2021
Download(s)
60
checked on Feb 18, 2021

Google ScholarTM
Check
Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.