Frank Wolter
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Frank Wolter has a total of 54 co-authors. Here are the top co-authors by number of shared publications:
- Michael Zakharyaschev
Birkbeck, University of London
8 shared publications - Carsten Lutz
Leipzig University
7 shared publications - Alessandro Artale
Free University of Bozen-Bolzano
6 shared publications - Jean Christoph Jung
TU Dortmund University
6 shared publications - Agi Kurucz
King's College London
5 shared publications - Michael Zakharyaschev
Birkbeck, University of London
5 shared publications
Latest Publications
- Open Access
- 5 November 2026
- Published by Ubiquity Press, Ltd.
- p. 326-369
From Interpolating Formulas to Separating Languages and Back Again
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.
- 5 November 2026
- Published by Ubiquity Press, Ltd.
- p. 326-369
Open AccessFrom Interpolating Formulas to Separating Languages and Back Again
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
- 5 November 2026
- Published by Ubiquity Press, Ltd.
- p. 1-33
Interpolation in Classical Propositional Logic
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.
- 5 November 2026
- Published by Ubiquity Press, Ltd.
- p. 1-33
Open AccessInterpolation in Classical Propositional Logic
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
- 5 November 2026
- Published by Ubiquity Press, Ltd.
Theory and Applications of Craig Interpolation
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.
- 5 November 2026
- Published by Ubiquity Press, Ltd.
Open AccessTheory and Applications of Craig Interpolation
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
- 27 October 2025
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 91 (3) , 1-52
A NON-UNIFORM VIEW OF CRAIG INTERPOLATION IN MODAL LOGICS WITH LINEAR FRAMES
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.- 27 October 2025
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 91 (3) , 1-52
Open AccessA NON-UNIFORM VIEW OF CRAIG INTERPOLATION IN MODAL LOGICS WITH LINEAR FRAMES
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
- 8 October 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic
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.- 8 October 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Open AccessDeciding the Existence of Interpolants and Definitions in First-Order Modal Logic
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
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 AccessComputation of Interpolants for Description Logic Concepts in Hard Cases
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
- 1 November 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 21 (1) , 82-93
Non-Rigid Designators in Modal and Temporal Free Description Logics
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.
- 1 November 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 21 (1) , 82-93
Open AccessNon-Rigid Designators in Modal and Temporal Free Description Logics
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
- 1 November 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 21 (1) , 487-497
Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology
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.
- 1 November 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 21 (1) , 487-497
Open AccessUnique Characterisability and Learnability of Temporal Queries Mediated by an Ontology
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
- 1 August 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 4, 3448-3456
Extremal Separation Problems for Temporal Instance Queries
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.
- 1 August 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 4, 3448-3456
Open AccessExtremal Separation Problems for Temporal Instance Queries
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.