Uniform interpolation via nested sequents and hypersequents

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F25%3A00604120" target="_blank" >RIV/67985807:_____/25:00604120 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1093/logcom/exae053" target="_blank" >https://doi.org/10.1093/logcom/exae053</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1093/logcom/exae053" target="_blank" >10.1093/logcom/exae053</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Uniform interpolation via nested sequents and hypersequents

Popis výsledku v původním jazyce

A modular proof-theoretic framework was recently developed to prove Craig interpolation for normal modal logics based on generalizations of sequent calculi (e.g. nested sequents, hypersequents and labelled sequents). In this paper, we turn to uniform interpolation, which is stronger than Craig interpolation. We develop a constructive method for proving uniform interpolation via nested sequents and apply it to reprove the uniform interpolation property for normal modal logics ⁠K, D and T⁠. We then use the know-how developed for nested sequents to apply the same method to hypersequents and obtain the first direct proof of uniform interpolation for S5 via a cut-free sequent-like calculus. While our method is proof-theoretic, the definition of uniform interpolation for nested sequents and hypersequents also uses semantic notions, including bisimulation modulo an atomic proposition.

Název v anglickém jazyce

Uniform interpolation via nested sequents and hypersequents

Popis výsledku anglicky

A modular proof-theoretic framework was recently developed to prove Craig interpolation for normal modal logics based on generalizations of sequent calculi (e.g. nested sequents, hypersequents and labelled sequents). In this paper, we turn to uniform interpolation, which is stronger than Craig interpolation. We develop a constructive method for proving uniform interpolation via nested sequents and apply it to reprove the uniform interpolation property for normal modal logics ⁠K, D and T⁠. We then use the know-how developed for nested sequents to apply the same method to hypersequents and obtain the first direct proof of uniform interpolation for S5 via a cut-free sequent-like calculus. While our method is proof-theoretic, the definition of uniform interpolation for nested sequents and hypersequents also uses semantic notions, including bisimulation modulo an atomic proposition.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Logic and Computation

ISSN

0955-792X

e-ISSN

1465-363X

Svazek periodika

35

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

23

Strana od-do

exae053

Kód UT WoS článku

001380316500001

EID výsledku v databázi Scopus

2-s2.0-105012041251