Complexity of monodic guarded fragments over linear and real time
File(s)moncx.pdf (322.54 KB)
Accepted version
Author(s)
Hodkinson, I
Type
Journal Article
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.
Version
Accepted version
Date Issued
2006
Citation
Annals of Pure and Applied Logic, 2006, 138 (1), pp.94-125
ISSN
0168-0072
Publisher
Elsevier Science Bv
Start Page
94
End Page
125
Journal / Book Title
Annals of Pure and Applied Logic
Volume
138
Issue
1
Copyright Statement
© 2005 Elsevier B.V. This is the author’s version of a work that was accepted for publication in Annals of Pure and Applied Logic. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Annals of Pure and Applied Logic, volume 138, issue 1-3 (March 2006). doi:10.1016/j.apat.2005.06.007.
Source Volume Number
138