1 citations · 2 across the 10 of their papers we have counts for
11 papers · 1 filter
Hypersequent Calculi Have Ackermannian Complexity
A. R. Balasubramanian, Vitor Greati, Revantha Ramanayake
For substructural logics with contraction or weakening admitting cut-free sequent calculi, proof search was analyzed using well-quasi-orders on (Dickson's lemma), yi…
Complexities of Well-Quasi-Ordered Substructural Logics
Nikolaos Galatos, Vitor Greati, Revantha Ramanayake +1
Substructural logics are formal logical systems that omit familiar structural rules of classical and intuitionistic logic such as contraction, weakening, exchange (commutativity),…
Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof
Manfred Borzechowski, Malvin Gattinger, Helle Hvid Hansen +3
We show that Propositional Dynamic Logic (PDL) has the Craig Interpolation Property. This question has been open for many years. Three proof attempts were published, but later crit…
Deducibility in the full Lambek calculus with weakening is HAck-complete
Vitor Greati, Revantha Ramanayake
We prove that the problem of deciding the consequence relation of the full Lambek calculus with weakening is complete for the class HAck of hyper-Ackermannian problems (i.e., level…
Internal and External Calculi: Ordering the Jungle without Being Lost in Translations
Tim S. Lyon, Agata Ciabattoni, Didier Galmiche +5
This paper gives a broad account of the various sequent-based proof formalisms in the proof-theoretic literature. We consider formalisms for various modal and tense logics, intuiti…
Cut-restriction: from cuts to analytic cuts
Agata Ciabattoni, Timo Lang, Revantha Ramanayake
Cut-elimination is the bedrock of proof theory with a multitude of applications from computational interpretations to proof analysis. It is also the starting point for important me…