JJJean Christoph Jung

Jean Christoph Jung

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Jean Christoph Jung has a total of 55 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Interpolation in Knowledge Representation

    by Jean Christoph Jung, Patrick Koopmann, Matthias Knorr

    Craig interpolation and uniform interpolation have many applications in knowledge representation, including explainability, forgetting, modularization and reuse, and even learning. At the same time, many relevant knowledge representation formalisms do in general not have Craig or uniform interpolation, and computing interpolants in practice is challenging. We have a closer look at two prominent knowledge representation formalisms, description logics and logic programming, and discuss theoretical results and practical methods for computing interpolants.

  • Open Access

    Theory and Applications of Craig Interpolation

    by Balder Ten Cate, Jean Christoph Jung, Patrick Koopmann, Christoph Wernhard, Frank Wolter

    Craig Interpolation and Beth Definability have played a central role in modern logic since the mid-twentieth century. Originating in William Craig’s and Evert Willem Beth’s pioneering work, they provide fundamental tools for understanding logical systems and how information can be transferred, transformed, or restricted within formal languages. Their impact extends across proof theory, model theory, philosophical logic, and computer science, where they illuminate both the power and the limitations of logical systems. This volume brings together leading researchers to offer a comprehensive and contemporary account of developments in interpolation and definability. The chapters range from classical insights to recent advances, covering a wide spectrum of topics. Readers will find in-depth investigations of interpolation in modal and superintuitionistic logics, algebraic perspectives on definability, and constructive approaches grounded in proof systems. Several contributions examine uniform interpolation and forgetting, shedding light on how logical content can be systematically simplified without losing relevant consequences. Others explore the crucial role of interpolation in automated reasoning, model checking, database querying, and ontology engineering, where interpolants serve as abstractors, separators, and explainers. A major theme of the volume is the meeting point between theory and application. While the contributors develop sophisticated mathematical techniques, they also demonstrate how these ideas support practical algorithms used in verification, querying, automated reasoning, and knowledge representation. The volume also pays tribute to Larisa Maksimova, whose groundbreaking work on interpolation in nonclassical logics continues to guide and inspire research in the field. Her contributions resonate through the topics discussed and the methods employed by many of the authors. Accessible to graduate students yet rich in material for specialists, this book offers an authoritative overview of Craig Interpolation and Beth Definability. It presents a broad and evolving research landscape, demonstrating how classical concepts remain essential in addressing contemporary questions about logical inference, expressiveness, and computation.

  • Open Access

    The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic

    by Jean Christoph Jung, JęDrzej Kołodziejski

    Modal separability for modal fixpoint formulae is the problem to decide for two given modal fixpoint formulae $φ,φ'$ whether there is a modal formula $ψ$ that separates them, in the sense that $φ\modelsψ$ and $ψ\models\negφ'$. We study modal separability and its special case modal definability over various classes of models, such as arbitrary models, finite models, trees, and models of bounded outdegree. Our main results are that modal separability is PSpace-complete over words, that is, models of outdegree $\leq 1$, ExpTime-complete over unrestricted and over binary models, and TwoExpTime-complete over models of outdegree bounded by some $d\geq 3$. Interestingly, this latter case behaves fundamentally different from the other cases also in that modal logic does not enjoy the Craig interpolation property over this class. Motivated by this we study also the induced interpolant existence problem as a special case of modal separability, and show that it is coNExpTime-complete and thus harder than validity in the logic. Besides deciding separability, we also provide algorithms for the effective construction of separators. Finally, we consider in a case study the extension of modal fixpoint formulae by graded modalities and investigate separability by modal formulae and graded modal formulae.

  • Open Access

    Fitting Ontologies and Constraints to Relational Structures

    by Simon Hosemann, Jean Christoph Jung, Carsten Lutz, Sebastian Rudolph

    We study the problem of fitting ontologies and constraints to positive and negative examples that take the form of a finite relational structure. As ontology and constraint languages, we consider the description logics EL and ELI as well as several classes of tuple-generating dependencies (TGDs): full, guarded, frontier-guarded, frontier-one, and unrestricted TGDs as well as inclusion dependencies. We pinpoint the exact computational complexity, design algorithms, and analyze the size of fitting ontologies and TGDs. We also investigate the related problem of constructing a finite basis of concept inclusions / TGDs for a given set of finite structures. While finite bases exist for EL, ELI, guarded TGDs, and inclusion dependencies, they in general do not exist for full, frontier-guarded and frontier-one TGDs.


  • SAT-Based Bounded Fitting for the Description Logic $\mathcal {ALC}$

    by Maurice Funk, Jean Christoph Jung, Tom Voellmer

  • Open Access

    SAT-Based Bounded Fitting for the Description Logic ALC

    by Maurice Funk, Jean Christoph Jung, Tom Voellmer

    Bounded fitting is a general paradigm for learning logical formulas from positive and negative data examples, that has received considerable interest recently. We investigate bounded fitting for the description logic ALC and its syntactic fragments. We show that the underlying size-restricted fitting problem is NP-complete for all studied fragments, even in the special case of a single positive and a single negative example. By design, bounded fitting comes with probabilistic guarantees in Valiant's PAC learning framework. In contrast, we show that other classes of algorithms for learning ALC concepts do not provide such guarantees. Finally, we present an implementation of bounded fitting in ALC and its fragments based on a SAT solver. We discuss optimizations and compare our implementation to other concept learning tools.

  • Open Access

    Computation of Interpolants for Description Logic Concepts in Hard Cases

    by Jean Christoph Jung, JęDrzej Kołodziejski, Frank Wolter

    While the computation of Craig interpolants for description logics (DLs) with the Craig Interpolation Property (CIP) is well understood, very little is known about the computation and size of interpolants for DLs without CIP or if one aims at interpolating concepts in a weaker DL than the DL of the input ontology and concepts. In this paper, we provide the first elementary algorithms computing (i) ALC-interpolants between ALC-concepts under ALCH-ontologies and (ii) ALC-interpolants between ALCQ-concepts under ALCQ-ontologies. The algorithms are based on recent decision procedures for interpolant existence. We also observe that, in contrast, uniform (possibly depth restricted) interpolants might be of non-elementary size.

  • Open Access

    Temporal Conjunctive Query Answering via Rewriting

    by Lukas Westhofen, Jean Christoph Jung, Daniel Neider

    Querying temporal data has recently gained traction in several artificial intelligence applications. As operational domains of intelligent agents are constantly being expanded, there is a strong need for representing domain knowledge. This comes in the form of ontologies, which are predominantly expressed in description logics and enrich time-stamped data to temporal knowledge bases. For modeling highly complex system environments, expressive description logics are often the formalism of choice. Querying such temporal knowledge bases is a challenging task, but recently a first practical solution has been put forward. We propose a novel approach to the query answering problem based on two well-known rewriting rules from temporal logic. After a careful theoretical analysis of our algorithm, we show in a practical evaluation on several benchmarks that it outperforms state of the art, sometimes by orders of magnitude. Based on our findings, we also propose a fragment of temporal conjunctive queries which guides users towards well-performing queries.


  • Open Access

    Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology

    by Jean Christoph Jung, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev

    Algorithms for learning database queries from examples and unique characterisations of queries by examples are prominent starting points for developing automated support for query explanation and construction. We investigate how far recent results and techniques on learning and unique characterisations of atemporal queries mediated by an ontology can be extended to temporal data and queries. Based on a systematic review of the relevant approaches in the atemporal case, we obtain general transfer results identifying conditions under which temporal queries composed of atemporal ones are (polynomially) learnable and uniquely characterisable.

  • Open Access

    Extremal Separation Problems for Temporal Instance Queries

    by Jean Christoph Jung, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev

    The separation problem for a class Q of database queries is to find a query in Q that distinguishes between a given set of ‘positive’ and ‘negative’ data examples. Separation provides explanations of examples and underpins the query-by-example paradigm to support database users in constructing and refining queries. As the space of all separating queries can be large, it is helpful to succinctly represent this space by means of its most specific (logically strongest) and general (weakest) members. We investigate this extremal separation problem for classes of instance queries formulated in linear temporal logic LTL with the operators conjunction, ‘next’, and ‘eventually’. Our results range from tight complexity bounds for verifying and counting extremal separators to algorithms computing them.