Implicational Relevance Logic is 2-EXPTIME-Complete
We show that provability in the implicational fragment of relevance logic is complete for doubly exponential time, using reductions to and from coverability in branching vector addition systems.
Researcher profile
Sylvain Schmitz
Sylvain Schmitz contributes to research discovery and scholarly infrastructure.
ResearcherAffiliation not importedOpen to collaborate
Trust snapshot
Quick read
Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
2topics
2close collaborators
Actions
Decide how to stay connected
Identity and collaboration
How to connect with this researcher
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Open a focused conversation when the fit is right
Claim this author entity first to unlock direct invitations.
Research graph
See the researcher in context
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
Building this graph slice
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
3 published item(s)
preprint2022arXiv
Non-Elementary Complexities for Branching VASS, MELL, and Extensions
We study the complexity of reachability problems on branching extensions of vector addition systems, which allows us to derive new non-elementary complexity bounds for fragments and variants of propositional linear logic. We show that provability in the multiplicative exponential fragment is Tower-hard already in the affine case -- and hence non-elementary. We match this lower bound for the full propositional affine linear logic, proving its Tower-completeness. We also show that provability in propositional contractive linear logic is Ackermann-complete.
0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv
Coverability is Undecidable in One-dimensional Pushdown Vector Addition Systems with Resets
We consider the model of pushdown vector addition systems with resets. These consist of vector addition systems that have access to a pushdown stack and have instructions to reset counters. For this model, we study the coverability problem. In the absence of resets, this problem is known to be decidable for one-dimensional pushdown vector addition systems, but decidability is open for general pushdown vector addition systems. Moreover, coverability is known to be decidable for reset vector addition systems without a pushdown stack. We show in this note that the problem is undecidable for one-dimensional pushdown vector addition systems with resets.
0 citations0 reviewsNo code linkedOpen access