Journal article icon

Journal article

Monadic datalog over finite structures of bounded treewidth.

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 l...

Expand abstract

Actions


Access Document


Publisher copy:
10.1145/1838552.1838555

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Journal:
ACM Trans. Comput. Log.
Volume:
12
Issue:
1
Pages:
3-3
Publication date:
2010-01-01
DOI:
EISSN:
1557-945X
ISSN:
1529-3785
URN:
uuid:f73eca07-b7d0-4c3c-afe5-8558cbf3fa56
Source identifiers:
301478
Local pid:
pubs:301478

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP