3.8k citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- University College LondonGB53 papers
- University of LondonGB49 papers
- Centre National de la Recherche ScientifiqueFR17 papers
- Free University of Bozen-BolzanoIT13 papers
- University of OxfordGB13 papers
- Imperial College LondonGB10 papers
- University of LiverpoolGB10 papers
- King's College LondonGB9 papers
- Institute for Nuclear Research and Nuclear EnergyBG8 papers
- University of ManchesterGB8 papers
- Johns Hopkins University Applied Physics LaboratoryUS7 papers
- The University of SydneyAU7 papers
27 papers · 1 filter
Fusions of One-Variable First-Order Modal Logics
Roman Kontchakov, Dmitry Shkatov, Frank Wolter
We investigate preservation results for the independent fusion of one-variable first-order modal logics. We show that, without equality, Kripke completeness and decidability of glo…
Logical Inferentialism & Attacks on Classical Logic
Khashayar Irani
This paper undertakes a foundational inquiry into logical inferentialism with particular emphasis on the normative standards it establishes and the implications these pose for clas…
Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic
Agi Kurucz, Frank Wolter, Michael Zakharyaschev
None of the first-order modal logics between and under the constant domain semantics enjoys Craig interpolation or projective Beth definability, even in…
Proof-Theoretic Semantics, a Problem with Negation and Prospects for Modality
Nils Kürbis
This paper discusses proof-theoretic semantics, the project of specifying the meanings of the logical constants in terms of rules of inference governing them. I concentrate on Mich…
First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic
Alessandro Artale, Roman Kontchakov, Alisa Kovtunova +3
We investigate ontology-based data access to temporal data. We consider temporal ontologies given in linear temporal logic LTL interpreted over discrete time (Z,<). Queries are giv…
Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics (Full Version)
Vladislav Ryzhikov, Przemyslaw Andrzej Walega, Michael Zakharyaschev
We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed w…
A static higher-order dependency pair framework
Carsten Fuhs, Cynthia Kop
We revisit the static dependency pair method for proving termination of higher-order term rewriting and extend it in a number of ways: (1) We introduce a new rewrite formalism desi…
Separation Logic with Linearly Compositional Inductive Predicates and Set Data Constraints
Chong Gao, Taolue Chen, Zhilin Wu
We identify difference-bound set constraints (DBS), an analogy of difference-bound arithmetic constraints for sets. DBS can express not only set constraints but also arithmetic con…
Domain and range for angelic and demonic compositions
Marcel Jackson, Szabolcs Mikulas
We give finite axiomatizations for the varieties generated by representable domain--range algebras when the semigroup operation is interpreted as angelic or demonic composition, re…
Kripke Completeness of Strictly Positive Modal Logics over Meet-semilattices with Operators
Stanislav Kikot, Agi Kurucz, Yoshihito Tanaka +2
Our concern is the completeness problem for spi-logics, that is, sets of implications between strictly positive formulas built from propositional variables, conjunction and modal d…
Querying Log Data with Metric Temporal Logic (Technical Report)
Sebastian Brandt, Elem Güzel Kalaycı, Vladislav Ryzhikov +2
We propose a novel framework for ontology-based access to temporal log data using a datalog extension datalogMTL of a Horn fragment of the metric temporal logic MTL. We show that d…
Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +2
We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded…
Horn Fragments of the Halpern-Shoham Interval Temporal Logic (Technical Report)
Davide Bresolin, Agi Kurucz, Emilio Muñoz-Velasco +3
We investigate the satisfiability problem for Horn fragments of the Halpern-Shoham interval temporal logic depending on the type (box or diamond) of the interval modal operators, t…
A Robust Class of Data Languages and an Application to Learning
Benedikt Bollig, Peter Habermehl, Martin Leucker +1
We introduce session automata, an automata model to process data words, i.e., words over an infinite alphabet. Session automata support the notion of fresh data values, which are w…
Verifying Procedural Programs via Constrained Rewriting Induction
Carsten Fuhs, Cynthia Kop, Naoki Nishida
This paper aims to develop a verification method for procedural programs via a transformation into Logically Constrained Term Rewriting Systems (LCTRSs). To this end, we extend tra…
The DL-Lite Family and Relations
Alessandro Artale, Diego Calvanese, Roman Kontchakov +1
The recently introduced series of description logics under the common moniker DL-Lite has attracted attention of the description logic and semantic web communities due to the low c…
On OBDDs for CNFs of bounded treewidth
Igor Razgon
In this paper we show that a CNF cannot be compiled into an Ordered Binary Decision Diagram (OBDD) of fixed-parameter size parameterized by the primal graph treewidth of the CNF. T…
The Complexity of Clausal Fragments of LTL
A. Artale, R. Kontchakov, V. Ryzhikov +1
We introduce and investigate a number of fragments of propo- sitional temporal logic LTL over the flow of time (Z, <). The fragments are defined in terms of the available temporal…
Temporal Description Logic for Ontology-Based Data Access (Extended Version)
Alessandro Artale, Roman Kontchakov, Frank Wolter +1
Our aim is to investigate ontology-based data access over temporal data with validity time and ontologies capable of temporal conceptual modelling. To this end, we design a tempora…
Cliquewidth and Knowledge Compilation
Igor Razgon, Justyna Petke
In this paper we study the role of cliquewidth in succinct representation of Boolean functions. Our main statement is the following: Let be a Boolean circuit having cliquewidth…
Taming the Infinite Chase: Query Answering under Expressive Integrity Constraints
Andrea Cali, Georg Gottlob, Michael Kifer
The chase algorithm is a fundamental tool for query evaluation and query containment under constraints, where the constraints are (sub-classes of) tuple-generating dependencies (TG…
A Cookbook for Temporal Conceptual Data Modelling with Description Logics
Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov +1
We design temporal description logics suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Li…
Exponential Lower Bounds and Separation for Query Rewriting
Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii +1
We establish connections between the size of circuits and formulas computing monotone Boolean functions and the size of first-order and nonrecursive Datalog rewritings for conjunct…
Topological Logics with Connectedness over Euclidean Spaces
Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann +1
We consider the quantifier-free languages, Bc and Bc0, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of b…