Complexity of monodic guarded fragments over linear and real time

Annals of Pure and Applied Logic 138 (1):94-125 (2006)

Abstract
We show that the satisfiability problem for the monodic guarded, loosely guarded, and packed fragments of first-order temporal logic with equality is 2Exptime-complete for structures with arbitrary first-order domains, over linear time, dense linear time, rational number time, and some other classes of linear flows of time. We then show that for structures with finite first-order domains, these fragments are also 2Exptime-complete over real number 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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2005.06.007
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,629
Through your library

References found in this work BETA

Model Theory.Wilfrid Hodges - 2008 - Stanford Encyclopedia of Philosophy.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.

View all 15 references / Add more references

Citations of this work BETA

The Complexity of Temporal Logic Over the Reals.Mark Reynolds - 2010 - Annals of Pure and Applied Logic 161 (8):1063-1096.

Add more citations

Similar books and articles

Guarded Fragments with Constants.Balder ten Cate & Massimo Franceschet - 2005 - Journal of Logic 14 (3):281-288.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Guarded Fragments with Constants.Balder ten Cate & Massimo Franceschet - 2005 - Journal of Logic, Language and Information 14 (3):281-288.
Guarded Quantification in Least Fixed Point Logic.Gregory McColm - 2004 - Journal of Logic, Language and Information 13 (1):61-110.
Linear-Time Temporal Logics with Presburger Constraints: An Overview ★.Stéphane Demri - 2006 - Journal of Applied Non-Classical Logics 16 (3-4):311-347.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Interpolation in Fragments of Classical Linear Logic.Dirk Roorda - 1994 - Journal of Symbolic Logic 59 (2):419-444.
On the Complexity of the Pancake Problem.Fuxiang Yu - 2007 - Mathematical Logic Quarterly 53 (4):532-546.
The Complexity of Horn Fragments of Linear Logic.Max I. Kanovich - 1994 - Annals of Pure and Applied Logic 69 (2-3):195-241.

Analytics

Added to PP index
2013-12-31

Total views
7 ( #924,134 of 2,280,567 )

Recent downloads (6 months)
1 ( #835,594 of 2,280,567 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature