FWFrank Wolter

Frank Wolter

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Frank Wolter has a total of 54 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    From Interpolating Formulas to Separating Languages and Back Again

    by Agi Kurucz, Frank Wolter, Michael Zakharyaschev

    Traditionally, research on Craig interpolation is concerned with (a) establishing the Craig interpolation property (CIP) of a logic saying that every valid implication in the logic has a Craig interpolant and (b) designing algorithms that extract Craig interpolants from proofs. Logics that lack the CIP are regarded as ‘pathological’ and excluded from consideration. In this chapter, we survey variations and generalisations of traditional Craig interpolation. First, we consider Craig interpolants for implications in logics without the CIP, focusing on the decidability and complexity of deciding their existence. We then generalise interpolation by looking for Craig interpolants in languages L′ that can be weaker than the language L of the given implication. Thus, do not only we restrict the non-logical symbols of Craig interpolants but also the logical ones. The resulting L/L′-interpolation problem generalises L/L′-definability, the question whether an L-formula is equivalent to some L′-formula. After that, we move from logical languages to formal languages where interpolation disguises itself as separation: given two disjoint languages in a class C, does there exist a separating language in a smaller class C′? This question is particularly well-studied in the case when the input languages are regular and the separating language is first-order definable. Finally, we connect the different research strands by showing how the decidability of the separation problem for regular languages can be used to prove the decidability of Craig interpolant existence for linear temporal logic LTL.

  • Open Access

    Interpolation in Classical Propositional Logic

    by Patrick Koopmann, Christoph Wernhard, Frank Wolter

    We introduce Craig interpolation and related notions such as uniform interpolation, Beth definability, and theory decomposition in classical propositional logic. We present four approaches to computing interpolants: via quantifier elimination, from formulas in disjunctive normal form, and by extraction from resolution or tableau refutations. We close with a discussion of the size of interpolants and links to circuit complexity.

  • 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

    A NON-UNIFORM VIEW OF CRAIG INTERPOLATION IN MODAL LOGICS WITH LINEAR FRAMES

    by Agi Kurucz, Frank Wolter, Michael Zakharyaschev

    Normal modal logics extending the logic $\mathsf {K4.3}$ of linear transitive frames are known to lack the Craig interpolation property (CIP), except some logics of bounded depth such as $\mathsf {S5}$ . We turn this ‘negative’ fact into a research question and pursue a non-uniform approach to Craig interpolation by investigating the following interpolant existence problem: decide whether there exists a Craig interpolant between two given formulas in any fixed logic above $\mathsf {K4.3}$ . Using a bisimulation-based characterisation of interpolant existence for descriptive frames, we show that this problem is decidable and coNP -complete for all finitely axiomatisable normal modal logics containing $\mathsf {K4.3}$ . It is thus not harder than entailment in these logics, which is in sharp contrast to other recent non-uniform interpolation results. We also extend our approach to Priorean temporal logics (with both past and future modalities) over the standard time flows—the integers, rationals, reals, and finite strict linear orders—none of which is blessed with the CIP.


  • Open Access

    Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic

    by Agi Kurucz, Frank Wolter, Michael Zakharyaschev

    None of the first-order modal logics between $\mathsf{K}$ and $\mathsf{S5}$ under the constant domain semantics enjoys Craig interpolation or projective Beth definability, even in the language restricted to a single individual variable. It follows that the existence of a Craig interpolant for a given implication or of an explicit definition for a given predicate cannot be directly reduced to validity as in classical first-order and many other logics. Our concern here is the decidability and computational complexity of the interpolant and definition existence problems. We first consider two decidable fragments of first-order modal logic $\mathsf{S5}$: the one-variable fragment $\mathsf{Q^1S5}$ and its extension $\mathsf{S5}_{\mathcal{ALC}^u}$ that combines $\mathsf{S5}$ and the description logic$\mathcal{ALC}$ with the universal role. We prove that interpolant and definition existence in $\mathsf{Q^1S5}$ and $\mathsf{S5}_{\mathcal{ALC}^u}$ is decidable in coN2ExpTime, being 2ExpTime-hard, while uniform interpolant existence is undecidable. These results transfer to the two-variable fragment $\mathsf{FO^2}$ of classical first-order logic without equality. We also show that interpolant and definition existence in the one-variable fragment $\mathsf{Q^1K}$ of first-order modal logic $\mathsf{K}$ is non-elementary decidable, while uniform interpolant existence is again undecidable.


  • 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

    Non-Rigid Designators in Modal and Temporal Free Description Logics

    by Alessandro Artale, Roman Kontchakov, Andrea Mazzullo, Frank Wolter

    Definite descriptions, such as ‘the General Chair of KR 2024’, are a semantically transparent device for object identification in knowledge representation. In first-order modal logic, definite descriptions have been widely investigated for their non-rigidity, which allows them to designate different objects (or none at all) at different states. We propose expressive modal description logics with non-rigid definite descriptions and names, and investigate decidability and complexity of the satisfiability problem. We first systematically link satisfiability for the one-variable fragment of first-order modal logic with counting to our modal description logics. Then, we prove a promising NEXPTIME-completeness result for concept satisfiability for the fundamental epistemic multi-agent logic S5n and its neighbours, and show that some expressive logics that are undecidable with constant domain become decidable (but Ackermann-hard) with expanding domains. Finally, we conduct a fine-grained analysis of decidability of temporal logics.

  • 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.