Imperial College London
Portrait Picture

Emeritus ProfessorIanHodkinson

Faculty of Engineering, Department of Computing

Emeritus Professor of Logic and Computation
 
 
 
//

Contact

 

i.hodkinson Website

 
 
//

Location

 

noneHuxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Hodkinson:2006,
author = {Hodkinson, I},
journal = {Annals of Pure and Applied Logic},
pages = {94--125},
title = {Complexity of monodic guarded fragments over linear and real time},
url = {http://hdl.handle.net/10044/1/623},
volume = {138},
year = {2006}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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.
AU  - Hodkinson,I
EP  - 125
PY  - 2006///
SN  - 0168-0072
SP  - 94
TI  - Complexity of monodic guarded fragments over linear and real time
T2  - Annals of Pure and Applied Logic
UR  - http://hdl.handle.net/10044/1/623
VL  - 138
ER  -
Download