Complexity of Hybrid Logics over Transitive Frames

Simple item page
dc.creatorMundhenk, Martin
dc.creatorSchneider, Thomas
dc.creatorSchwentick, Thomas
dc.creatorWeber, Volker
dc.date2008-06-25
dc.date.accessioned2026-07-07T12:19:41Z
dc.date.available2026-07-07T12:19:41Z
dc.descriptionThis paper examines the complexity of hybrid logics over transitive frames, transitive trees, and linear frames. We show that satisfiability over transitive frames for the hybrid language extended with the downarrow operator is NEXPTIME-complete. This is in contrast to undecidability of satisfiability over arbitrary frames for this language (Areces, Blackburn, Marx 1999). It is also shown that adding the @ operator or the past modality leads to undecidability over transitive frames. This is again in contrast to the case of transitive trees and linear frames, where we show these languages to be nonelementarily decidable. Moreover, we establish 2EXPTIME and EXPTIME upper bounds for satisfiability over transitive frames and transitive trees, respectively, for the hybrid Until/Since language. An EXPTIME lower bound is shown to hold for the modal Until language over both frame classes.
dc.description21 pages, 6 figures (only 2 thereof are in external files)
dc.identifierhttps://arxiv.org/abs/0806.4130
dc.identifierhttp://arxiv.org/abs/0806.4130
dc.identifierWorkshop "Methods for Modalities" (M4M-4), Informatik-Berichte, 194, pp. 62-78, 2005. ISSN 0863-095X
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/212840
dc.subjectLogic in Computer Science
dc.subjectF.4.1
dc.titleComplexity of Hybrid Logics over Transitive Frames
dc.typetext

Files

Collections

arXiv