Computing Publications

Publications Home » Complexity of monodic guarded fra...

Complexity of monodic guarded fragments over linear and real time

Ian Hodkinson

Journal Article
Annals of Pure and Applied Logic
Volume 138
Issues 1–3
pp.94–125
2006
Elsevier Science Bv
ISSN 0168-0072
Abstract

We show that the satisfiability problem for the monodic guarded and packed fragments with equality and arbitrary first-order domains over linear time, dense linear time, rational numbers time, and some other classes of linear flows of time, is 2Exptime-complete. We then show that with finite first-order domains, these fragments are also 2Exptime-complete over real numbers time, and (hence) over most of the commonly-used linear flows of time, including the natural numbers, integers, rationals, and any first-order definable class of linear flows of time.

PDF of full publication (287 kilobytes)
(need help viewing PDF files?)
BibTEX file for the publication
N.B.
Conditions for downloading publications from this site.
 

pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.