17 found
Order:
  1.  3
    An Introduction to Description Logic.Franz Baader, Ian Horrocks, Carsten Lutz & Uli Sattler - 2017 - Cambridge, England: Cambridge University Press.
    The first introductory textbook on description logics, relevant to computer science, knowledge representation and the semantic web.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2. Temporalising tableaux.Roman Kontchakov, Carsten Lutz, Frank Wolter & Michael Zakharyaschev - 2004 - Studia Logica 76 (1):91 - 134.
    As a remedy for the bad computational behaviour of first-order temporal logic (FOTL), it has recently been proposed to restrict the application of temporal operators to formulas with at most one free variable thereby obtaining so-called monodic fragments of FOTL. In this paper, we are concerned with constructing tableau algorithms for monodic fragments based on decidable fragments of first-order logic like the two-variable fragment or the guarded fragment. We present a general framework that shows how existing decision procedures for first-order (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  3.  2
    Query inseparability for ALC ontologies.Elena Botoeva, Carsten Lutz, Vladislav Ryzhikov, Frank Wolter & Michael Zakharyaschev - 2019 - Artificial Intelligence 272 (C):1-51.
  4. The Complexity of Reasoning with Boolean Modal Logics.Carsten Lutz & Ulrike Sattler - 2002 - In Frank Wolter, Heinrich Wansing, Maarten de Rijke & Michael Zakharyaschev (eds.), Advances in Modal Logic, Volume 3. CSLI Publications. pp. 329-348.
    No categories
     
    Export citation  
     
    Bookmark   5 citations  
  5.  1
    -Connections of abstract description systems.Oliver Kutz, Carsten Lutz, Frank Wolter & Michael Zakharyaschev - 2004 - Artificial Intelligence 156 (1):1-73.
  6. Model-theoretic inseparability and modularity of description logic ontologies.Boris Konev, Carsten Lutz, Dirk Walther & Frank Wolter - 2013 - Artificial Intelligence 203 (C):66-103.
  7.  32
    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  
  8. Foundations of instance level updates in expressive description logics.Hongkai Liu, Carsten Lutz, Maja Miličić & Frank Wolter - 2011 - Artificial Intelligence 175 (18):2170-2197.
  9.  4
    Logical separability of labeled data examples under ontologies.Jean Christoph Jung, Carsten Lutz, Hadrien Pulcini & Frank Wolter - 2022 - Artificial Intelligence 313 (C):103785.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  15
    PDL with negation of atomic programs.Carsten Lutz & Dirk Walther - 2005 - Journal of Applied Non-Classical Logics 15 (2):189-213.
    Propositional dynamic logic is one of the most successful variants of modal logic. To make it even more useful for applications, many extensions of PDL have been considered in the literature. A very natural and useful such extension is with negation of programs. Unfortunately, as long-known, reasoning with the resulting logic is undecidable. In this paper, we consider the extension of PDL with negation of atomic programs, only. We argue that this logic is still useful, e.g. in the context of (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  11.  78
    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  
  12.  82
    A tableau decision algorithm for modalized ALC with constant domains.Carsten Lutz, Holger Sturm, Frank Wolter & Michael Zakharyaschev - 2002 - Studia Logica 72 (2):199-232.
    The aim of this paper is to construct a tableau decision algorithm for the modal description logic K ALC with constant domains. More precisely, we present a tableau procedure that is capable of deciding, given an ALC-formula with extra modal operators (which are applied only to concepts and TBox axioms, but not to roles), whether is satisfiable in a model with constant domains and arbitrary accessibility relations. Tableau-based algorithms have been shown to be practical even for logics of rather high (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  13. Combining interval-based temporal reasoning with general TBoxes.Carsten Lutz - 2004 - Artificial Intelligence 152 (2):235-274.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  3
    A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL.Carsten Lutz & Leif Sabellek - 2022 - Artificial Intelligence 308 (C):103709.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  13
    A Correspondence between Temporal Description Logics.Alessandro Artale & Carsten Lutz - 2004 - Journal of Applied Non-Classical Logics 14 (1-2):209-233.
    In this paper, we investigate the relationship between two decidable interval-based temporal description logics that have been proposed in the literature, T L-ALCF and ALCF. Although many aspects of these two logics are quite similar, the two logics suggest two rather different paradigms for representing temporal conceptual knowledge. In this paper, we exhibit a reduction from T L-ALCF concepts to ALCF concepts that serves two purposes: first, it nicely illustrates the relationship between the two knowledge representation paradigms; and second, it (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  6
    Description Logics with Concrete Domains- A Survey.Carsten Lutz - 2003 - In Philippe Balbiani, Nobu-Yuki Suzuki, Frank Wolter & Michael Zakharyaschev (eds.), Advances in Modal Logic, Volume 4. CSLI Publications. pp. 265-296.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  8
    A complete system of four-valued logic.P. H. Rodenburg & Carsten Lutz - 2001 - Journal of Applied Non-Classical Logics 11 (3-4):367-392.