7 papers
The logic of bunched implications is undecidable
Nick Galatos, Peter Jipsen, Søren Brinck Knudstorp +1
The logic of bunched implications (BI), introduced by O'Hearn and Pym (1999), has attracted significant attention due to its elegant proof calculus, varied semantics, and close con…
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…
A syntactic proof of decidability for the logic of bunched implication BI
Revantha Ramanayake
The logic of bunched implication BI provides a framework for reasoning about resource composition and forms the basis for an assertion language of separation logic which is used to…
Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
Amirhossein Akbar Tabatabai, Vitor Greati, Revantha Ramanayake
Inspired by Leivant's work on absolute predicativism, Bellantoni and Cook in 1992 introduced a structurally restricted form of recursion called predicative recursion. Using this re…
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…
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),…