Agi Kurucz
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
Agi Kurucz has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Frank Wolter
University of Liverpool
5 shared publications - Stanislav Kikot
Moscow State University
5 shared publications - Michael Zakharyaschev
Birkbeck, University of London
4 shared publications - Roman Kontchakov
Birkbeck, University of London
4 shared publications - Christopher Hampson
King’s College
3 shared publications F. Wolter
3 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
- 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
Deciding FO-rewritability of regular languages and ontology-mediated queries in Linear Temporal Logic
Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) formulated in linear temporal logic LTL over (Z,<) and deciding whether it is rewritable to an FO(<)-query, possibly with some extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering in AC^0, ACC^0 and NC^1 coincides with FO(<,\equiv)-rewritability using unary predicates x \equiv 0 (mod n), FO(<,MOD)-rewritability, and FO(RPR)-rewritability using relational primitive recursion, respectively. We prove that, similarly to known PSPACE-completeness of recognising FO(<)-definability of regular languages, deciding FO(<,\equiv)- and FO(<,MOD)-definability is also \PSPACE-complete (unless ACC^0 = NC^1). We then use this result to show that deciding FO(<)-, FO(<,\equiv)- and FO(<,MOD)-rewritability of LTL OMQs is EXPSPACE-complete, and that these problems become PSPACE-complete for OMQs with a linear Horn ontology and an atomic query, and also a positive query in the cases of FO(<)- and FO(<,\equiv)-rewritability. Further, we consider FO(<)-rewritability of OMQs with a binary-clause ontology and identify OMQ classes, for which deciding it is PSPACE-, Pi_2^p- and coNP-complete.
Open AccessDeciding FO-rewritability of regular languages and ontology-mediated queries in Linear Temporal Logic
Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) formulated in linear temporal logic LTL over (Z,<) and deciding whether it is rewritable to an FO(<)-query, possibly with some extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering in AC^0, ACC^0 and NC^1 coincides with FO(<,\equiv)-rewritability using unary predicates x \equiv 0 (mod n), FO(<,MOD)-rewritability, and FO(RPR)-rewritability using relational primitive recursion, respectively. We prove that, similarly to known PSPACE-completeness of recognising FO(<)-definability of regular languages, deciding FO(<,\equiv)- and FO(<,MOD)-definability is also \PSPACE-complete (unless ACC^0 = NC^1). We then use this result to show that deciding FO(<)-, FO(<,\equiv)- and FO(<,MOD)-rewritability of LTL OMQs is EXPSPACE-complete, and that these problems become PSPACE-complete for OMQs with a linear Horn ontology and an atomic query, and also a positive query in the cases of FO(<)- and FO(<,\equiv)-rewritability. Further, we consider FO(<)-rewritability of OMQs with a binary-clause ontology and identify OMQ classes, for which deciding it is PSPACE-, Pi_2^p- and coNP-complete.
- Open Access
- 13 May 2022
- Published by Elsevier in Artificial Intelligence
- Vol. 309
A tetrachotomy of ontology-mediated queries with a covering axiom
- 13 May 2022
- Published by Elsevier in Artificial Intelligence
- Vol. 309
Open AccessA tetrachotomy of ontology-mediated queries with a covering axiom
- 1 May 2020
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 171 (5) , 102786
Non-finitely axiomatisable modal product logics with infinite canonical axiomatisations
- 1 May 2020
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 171 (5) , 102786
Non-finitely axiomatisable modal product logics with infinite canonical axiomatisations
- Open Access
- 3 April 2019
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 84 (2) , 533-588
KRIPKE COMPLETENESS OF STRICTLY POSITIVE MODAL LOGICS OVER MEET-SEMILATTICES WITH OPERATORS
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 diamond operators. Originated in logic, algebra and computer science, spi-logics have two natural semantics: meet-semilattices with monotone operators providing Birkhoff-style calculi and first-order relational structures (aka Kripke frames) often used as the intended structures in applications. Here we lay foundations for a completeness theory that aims to answer the question whether the two semantics define the same consequence relations for a given spi-logic.
- 3 April 2019
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 84 (2) , 533-588
Open AccessKRIPKE COMPLETENESS OF STRICTLY POSITIVE MODAL LOGICS OVER MEET-SEMILATTICES WITH OPERATORS
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 diamond operators. Originated in logic, algebra and computer science, spi-logics have two natural semantics: meet-semilattices with monotone operators providing Birkhoff-style calculi and first-order relational structures (aka Kripke frames) often used as the intended structures in applications. Here we lay foundations for a completeness theory that aims to answer the question whether the two semantics define the same consequence relations for a given spi-logic.
- Open Access
Kripke Completeness of Strictly Positive Modal Logics over Meet-semilattices with Operators
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 diamond operators. Originated in logic, algebra and computer science, spi-logics have two natural semantics: meet-semilattices with monotone operators providing Birkhoff-style calculi, and first-order relational structures (aka Kripke frames) often used as the intended structures in applications. Here we lay foundations for a completeness theory that aims to answer the question whether the two semantics define the same consequence relations for a given spi-logic.
Open AccessKripke Completeness of Strictly Positive Modal Logics over Meet-semilattices with Operators
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 diamond operators. Originated in logic, algebra and computer science, spi-logics have two natural semantics: meet-semilattices with monotone operators providing Birkhoff-style calculi, and first-order relational structures (aka Kripke frames) often used as the intended structures in applications. Here we lay foundations for a completeness theory that aims to answer the question whether the two semantics define the same consequence relations for a given spi-logic.
- Open Access
- 18 February 2016
- Published by Springer Nature in Studia Logica
- Vol. 104 (3) , 455-486
The Decision Problem of Modal Product Logics with a Diagonal, and Faulty Counter Machines
- 18 February 2016
- Published by Springer Nature in Studia Logica
- Vol. 104 (3) , 455-486
Open AccessThe Decision Problem of Modal Product Logics with a Diagonal, and Faulty Counter Machines
- Open Access
- 8 July 2015
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 16 (3) , 1-36
Undecidable Propositional Bimodal Logics and One-Variable First-Order Linear Temporal Logics with Counting
First-order temporal logics are notorious for their bad computational behavior. It is known that even the two-variable monadic fragment is highly undecidable over various linear timelines, and over branching time even one-variable fragments might be undecidable. However, there have been several attempts at finding well-behaved fragments of first-order temporal logics and related temporal description logics, mostly either by restricting the available quantifier patterns or by considering sub-Boolean languages. Here we analyze seemingly “mild” extensions of decidable one-variable fragments with counting capabilities, interpreted in models with constant, decreasing, and expanding first-order domains. We show that over most classes of linear orders, these logics are (sometimes highly) undecidable, even without constant and function symbols, and with the sole temporal operator “eventually.” We establish connections with bimodal logics over 2D product structures having linear and “difference” (inequality) component relations and prove our results in this bimodal setting. We show a general result saying that satisfiability over many classes of bimodal models with commuting “unbounded” linear and difference relations is undecidable. As a byproduct, we also obtain new examples of finitely axiomatizable but Kripke incomplete bimodal logics. Our results generalize similar lower bounds on bimodal logics over products of two linear relations, and our proof methods are quite different from the known proofs of these results. Unlike previous proofs that first “diagonally encode” an infinite grid and then use reductions of tiling or Turing machine problems, here we make direct use of the grid-like structure of product frames and obtain lower-complexity bounds by reductions of counter (Minsky) machine problems. Representing counter machine runs apparently requires less control over neighboring grid points than tilings or Turing machine runs, and so this technique is possibly more versatile, even if one component of the underlying product structures is “close to” being the universal relation.
- 8 July 2015
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 16 (3) , 1-36
Open AccessUndecidable Propositional Bimodal Logics and One-Variable First-Order Linear Temporal Logics with Counting
First-order temporal logics are notorious for their bad computational behavior. It is known that even the two-variable monadic fragment is highly undecidable over various linear timelines, and over branching time even one-variable fragments might be undecidable. However, there have been several attempts at finding well-behaved fragments of first-order temporal logics and related temporal description logics, mostly either by restricting the available quantifier patterns or by considering sub-Boolean languages. Here we analyze seemingly “mild” extensions of decidable one-variable fragments with counting capabilities, interpreted in models with constant, decreasing, and expanding first-order domains. We show that over most classes of linear orders, these logics are (sometimes highly) undecidable, even without constant and function symbols, and with the sole temporal operator “eventually.” We establish connections with bimodal logics over 2D product structures having linear and “difference” (inequality) component relations and prove our results in this bimodal setting. We show a general result saying that satisfiability over many classes of bimodal models with commuting “unbounded” linear and difference relations is undecidable. As a byproduct, we also obtain new examples of finitely axiomatizable but Kripke incomplete bimodal logics. Our results generalize similar lower bounds on bimodal logics over products of two linear relations, and our proof methods are quite different from the known proofs of these results. Unlike previous proofs that first “diagonally encode” an infinite grid and then use reductions of tiling or Turing machine problems, here we make direct use of the grid-like structure of product frames and obtain lower-complexity bounds by reductions of counter (Minsky) machine problems. Representing counter machine runs apparently requires less control over neighboring grid points than tilings or Turing machine runs, and so this technique is possibly more versatile, even if one component of the underlying product structures is “close to” being the universal relation.