Paper Info
Title
Hybrid Logics on Linear Structures: Expressivity and Complexity
Abstract
We investigate expressivity and complexity of hybrid log- ics on linear structures. Hybrid logics are an enrichment of modal logics with certain first-order features which are al- gorithmically well behaved. Therefore, they are well suited for the specification of certain properties of computational systems. We show that hybrid logics are more expressive than usual modal and temporal logics on linear structures, and exhibit a hierarchy of hybrid languages. We determine the complexities of the satisfiability problem for these lan- guages and define an existential fragment of hybrid logic for which satisfiability is still NP-complete. Finally, we ex- amine the linear time model checking problem for hybrid logics and its complexity.
Year
DOI
Venue
2003
10.1109/TIME.2003.1214893
TIME
Keywords
Field
DocType
linear time,model checking,satisfiability,modal logic,temporal logic,first order
Computation tree logic,Hybrid logic,T-norm fuzzy logics,Model checking,Accessibility relation,Kripke semantics,Computer science,Theoretical computer science,Monoidal t-norm logic,Classical logic
Conference
Citations 
PageRank 
References 
14
0.67
9
Authors
3
Name
Order
Citations
PageRank
Massimo Franceschet165839.91
Maarten de Rijke26516509.76
Bernd-holger Schlingloff319519.56