Uniform Lyndon Interpolation for Basic Non-normal Modal and Conditional Logics

Raheleh Jalali; Rosalie Iemhoff; Amirhossein  Akbar Tabatabai

doi:10.1093/logcom/exae057

Uniform Lyndon Interpolation for Basic Non-normal Modal and Conditional Logics

Raheleh Jalali, Rosalie Iemhoff, Amirhossein Akbar Tabatabai

Department of Computer Science

Utrecht University

Research output: Contribution to journal › Article › peer-review

1 Citation (SciVal)

Abstract

In this paper, a proof-theoretic method to prove uniform Lyndon interpolation (ULIP) for non-normal modal and conditional logics is introduced and applied to show that the logics, E, M, EN, MN, MC, K, and their conditional versions, CE, CM, CEN,CMN, CMC, CK, in addition to CKID have that property. In particular, it implies that these logics have uniform interpolation (UIP). Although for some of them the latter is known, the fact that they have uniform LIP is new. Also, the proof-theoretic proofs of these facts are new, as well as the constructive way to explicitly compute the interpolants that they provide. On the negative side, it is shown that the logics CKCEM and CKCEMID enjoy UIP but not uniform LIP. Moreover, it is proved that the non-normal modal logics, EC and ECN, and their conditional versions, CEC and CECN, do not have Craig interpolation, and whence no uniform (Lyndon) interpolation.

Original language	English
Article number	exae057
Number of pages	30
Journal	Journal of Logic and Computation
Volume	35
Issue number	6
Early online date	17 Nov 2024
DOIs	https://doi.org/10.1093/logcom/exae057
Publication status	Published - 1 Sept 2025

Acknowledgements

We thank Iris van der Giessen for fruitful discussions on the topic of this paper and three referees for comments that helped improving the paper.

Funding

Support by the Netherlands Organisation for Scientific Research under grant 639.073.807 and by the MOSAIC project (EU H2020-MSCA-RISE-2020 Project 101007627) is gratefully acknowledged.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	639.073.807, 101007627

Keywords

Craig interpolation
conditional logics
non-normal modal logics
uniform Lyndon interpolation
uniform interpolation

ASJC Scopus subject areas

Theoretical Computer Science
Software
Arts and Humanities (miscellaneous)
Hardware and Architecture
Logic

Access to Document

10.1093/logcom/exae057Licence: CC BY-NC-ND

Cite this

@article{6a44edac0102409083cda3d28c4927c7,

title = "Uniform Lyndon Interpolation for Basic Non-normal Modal and Conditional Logics",

abstract = "In this paper, a proof-theoretic method to prove uniform Lyndon interpolation (ULIP) for non-normal modal and conditional logics is introduced and applied to show that the logics, E, M, EN, MN, MC, K, and their conditional versions, CE, CM, CEN,CMN, CMC, CK, in addition to CKID have that property. In particular, it implies that these logics have uniform interpolation (UIP). Although for some of them the latter is known, the fact that they have uniform LIP is new. Also, the proof-theoretic proofs of these facts are new, as well as the constructive way to explicitly compute the interpolants that they provide. On the negative side, it is shown that the logics CKCEM and CKCEMID enjoy UIP but not uniform LIP. Moreover, it is proved that the non-normal modal logics, EC and ECN, and their conditional versions, CEC and CECN, do not have Craig interpolation, and whence no uniform (Lyndon) interpolation.",

keywords = "Craig interpolation, conditional logics, non-normal modal logics, uniform Lyndon interpolation, uniform interpolation",

author = "Raheleh Jalali and Rosalie Iemhoff and \{Akbar Tabatabai\}, Amirhossein",

year = "2025",

month = sep,

day = "1",

doi = "10.1093/logcom/exae057",

language = "English",

volume = "35",

journal = "Journal of Logic and Computation",

issn = "0955-792X",

publisher = "Oxford University Press",

number = "6",

}

TY - JOUR

T1 - Uniform Lyndon Interpolation for Basic Non-normal Modal and Conditional Logics

AU - Jalali, Raheleh

AU - Iemhoff, Rosalie

AU - Akbar Tabatabai, Amirhossein

PY - 2025/9/1

Y1 - 2025/9/1

N2 - In this paper, a proof-theoretic method to prove uniform Lyndon interpolation (ULIP) for non-normal modal and conditional logics is introduced and applied to show that the logics, E, M, EN, MN, MC, K, and their conditional versions, CE, CM, CEN,CMN, CMC, CK, in addition to CKID have that property. In particular, it implies that these logics have uniform interpolation (UIP). Although for some of them the latter is known, the fact that they have uniform LIP is new. Also, the proof-theoretic proofs of these facts are new, as well as the constructive way to explicitly compute the interpolants that they provide. On the negative side, it is shown that the logics CKCEM and CKCEMID enjoy UIP but not uniform LIP. Moreover, it is proved that the non-normal modal logics, EC and ECN, and their conditional versions, CEC and CECN, do not have Craig interpolation, and whence no uniform (Lyndon) interpolation.

AB - In this paper, a proof-theoretic method to prove uniform Lyndon interpolation (ULIP) for non-normal modal and conditional logics is introduced and applied to show that the logics, E, M, EN, MN, MC, K, and their conditional versions, CE, CM, CEN,CMN, CMC, CK, in addition to CKID have that property. In particular, it implies that these logics have uniform interpolation (UIP). Although for some of them the latter is known, the fact that they have uniform LIP is new. Also, the proof-theoretic proofs of these facts are new, as well as the constructive way to explicitly compute the interpolants that they provide. On the negative side, it is shown that the logics CKCEM and CKCEMID enjoy UIP but not uniform LIP. Moreover, it is proved that the non-normal modal logics, EC and ECN, and their conditional versions, CEC and CECN, do not have Craig interpolation, and whence no uniform (Lyndon) interpolation.

KW - Craig interpolation

KW - conditional logics

KW - non-normal modal logics

KW - uniform Lyndon interpolation

KW - uniform interpolation

UR - https://www.scopus.com/pages/publications/105011943077

U2 - 10.1093/logcom/exae057

DO - 10.1093/logcom/exae057

M3 - Article

SN - 0955-792X

VL - 35

JO - Journal of Logic and Computation

JF - Journal of Logic and Computation

IS - 6

M1 - exae057

ER -

Uniform Lyndon Interpolation for Basic Non-normal Modal and Conditional Logics

Abstract

Acknowledgements

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this