Switch to: References

Add citations

You must login to add citations.
  1. Complexity of Hybrid Logics Over Transitive Frames.Martin Mundhenk, Thomas Schneider, Thomas Schwentick & Volker Weber - 2010 - Journal of Applied Logic 8 (4):422-440.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • PDL with Intersection and Converse: Satisfiability and Infinite-State Model Checking.Stefan Göller, Markus Lohrey & Carsten Lutz - 2009 - Journal of Symbolic Logic 74 (1):279-314.
    We study satisfiability and infinite-state model checking in ICPDL, which extends Propositional Dynamic Logic (PDL) with intersection and converse operators on programs. The two main results of this paper are that (i) satisfiability is in 2EXPTIME, thus 2EXPTIME-complete by an existing lower bound, and (ii) infinite-state model checking of basic process algebras and pushdown systems is also 2EXPTIME-complete. Both upper bounds are obtained by polynomial time computable reductions to ω-regular tree satisfiability in ICPDL, a reasoning problem that we introduce specifically (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Inessential Features, Ineliminable Features, and Modal Logics for Model Theoretic Syntax.Hans-Jörg Tiede - 2008 - Journal of Logic, Language and Information 17 (2):217-227.
    While monadic second-order logic (MSO) has played a prominent role in model theoretic syntax, modal logics have been used in this context since its inception. When comparing propositional dynamic logic (PDL) to MSO over trees, Kracht (1997) noted that there are tree languages that can be defined in MSO that can only be defined in PDL by adding new features whose distribution is predictable. He named such features “inessential features”. We show that Kracht’s observation can be extended to other modal (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • 2-Exp Time Lower Bounds for Propositional Dynamic Logics with Intersection.Martin Lange & Carsten Lutz - 2005 - Journal of Symbolic Logic 70 (4):1072-1086.
    In 1984, Danecki proved that satisfiability in IPDL, i.e., Propositional Dynamic Logic (PDL) extended with an intersection operator on programs, is decidable in deterministic double exponential time. Since then, the exact complexity of IPDL has remained an open problem: the best known lower bound was the ExpTime one stemming from plain PDL until, in 2004, the first author established ExpSpace-hardness. In this paper, we finally close the gap and prove that IPDL is hard for 2-ExpTime, thus 2-ExpTime-complete. We then sharpen (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Complexity of Modal Logics with Presburger Constraints.Stéphane Demri & Denis Lugiez - 2010 - Journal of Applied Logic 8 (3):233-252.