NDLI: Monadic datalog over finite structures of bounded treewidth

Please wait, while we are loading the content...

Monadic datalog over finite structures of bounded treewidth

Content Provider	ACM Digital Library
Author	Pichler, Reinhard Wei, Fang Gottlob, Georg
Copyright Year	2010
Abstract	Bounded treewidth and monadic second-order (MSO) logic have proved to be key concepts in establishing fixed-parameter tractability results. Indeed, by Courcelle's Theorem we know that any property of finite structures, which is expressible by an MSO sentence, can be decided in linear time (data complexity) if the structures have bounded treewidth. In principle, Courcelle's Theorem can be applied directly to construct concrete algorithms by transforming the MSO evaluation problem into a tree language recognition problem. The latter can then be solved via a finite tree automaton (FTA). However, this approach has turned out to be problematical, since even relatively simple MSO formulae may lead to a “state explosion” of the FTA. In this work we propose monadic datalog (i.e., datalog where all intentional predicate symbols are unary) as an alternative method to tackle this class of fixed-parameter tractable problems. We show that if some property of finite structures is expressible in MSO then this property can also be expressed by means of a monadic datalog program over the decomposed structure: we mean by this that the original structure is augmented with new elements and new relations that encode one of its tree decompositions. In the first place, we thus compare the expressive power of two query languages. However, we also show that the resulting fragment of datalog can be evaluated in linear time (both with respect to the program size and with respect to the data size). Hence, our transformation of an MSO query into a monadic datalog program yields an alternative proof of Courcelle's Theorem. In order to actually construct efficient algorithms for problems whose tractability is due to Courcelle's Theorem, we propose to use a fragment of full (i.e., not necessarily monadic) datalog which allows for a succinct representation of the corresponding monadic datalog programs and for an efficient execution. This new approach is put to work by devising datalog programs for the 3-Colorability problem of graphs and for the PRIMALITY problem of relational schemas (i.e., testing if some attribute in a relational schema is part of a key). We also report on experimental results with a prototype implementation.
Starting Page	1
Ending Page	48
Page Count	48
File Format	PDF
ISSN	15293785
e-ISSN	1557945X
DOI	10.1145/1838552.1838555
Volume Number	12
Issue Number	1
Journal	ACM Transactions on Computational Logic (TOCL)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-11-26
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Datalog Monadic second-order logic Fixed-parameter tractability Tree decomposition Treewidth
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Logic Computational Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Monadic datalog over finite structures with bounded treewidth

Monadic Datalog over Finite Structures with Bounded Treewidth (2007)

Monadic datalog over finite structures with bounded treewidth (2007)

Enumeration of monadic second-order queries on trees

Automata-theoretic and datalog-based solutions of monadic second-order logic evaluation problems over structures of bounded-treewidth

Automata-theoretic and datalog-based solutions of monadic second-order logic evaluation problems over structures of bounded-treewidth (2011).

Where First-Order and Monadic Second-Order Logic Coincide

Monadic Datalog over Finite Structures with Bounded Treewidth

A hierarchical approach to monadic second-order logic over graphs (1997).

Monadic datalog over finite structures of bounded treewidth

Similar Documents

Monadic datalog over finite structures with bounded treewidth

Monadic Datalog over Finite Structures with Bounded Treewidth (2007)

Monadic datalog over finite structures with bounded treewidth (2007)

Enumeration of monadic second-order queries on trees

Automata-theoretic and datalog-based solutions of monadic second-order logic evaluation problems over structures of bounded-treewidth

Automata-theoretic and datalog-based solutions of monadic second-order logic evaluation problems over structures of bounded-treewidth (2011).

Where First-Order and Monadic Second-Order Logic Coincide

Monadic Datalog over Finite Structures with Bounded Treewidth

A hierarchical approach to monadic second-order logic over graphs (1997).

Monadic datalog over finite structures of bounded treewidth