The complexity of decision procedures in relevance logic II

DOI10.2307/2586811zbMath0945.03029OpenAlexW4234015612MaRDI QIDQ4948542

Alasdair Urquhart

Publication date: 28 June 2000

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2586811

zbMATH Keywords

upper boundAckermann functiondecision procedurelower bound on the complexityimplication-conjunction fragments

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47) Complexity of proofs (03F20)

Related Items (12)

Current trends in substructural logics ⋮ Nonelementary Complexities for Branching VASS, MELL, and Extensions ⋮ MOST SIMPLE EXTENSIONS OF ARE UNDECIDABLE ⋮ Varieties of De Morgan monoids: minimality and irreducible algebras ⋮ On the decision problem for MELL ⋮ A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets ⋮ Non-primitive recursive decidability of products of modal logics with expanding domains ⋮ The ideal view on Rackoff's coverability technique ⋮ On the termination and structural termination problems for counter machines with incrementing errors ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary ⋮ A Logical Autobiography

Uses Software

• KRIPKE

Cites Work

• Unnamed Item
• Unnamed Item
• Petri nets and large finite sets
• Decision problems for propositional linear logic
• Parallel program schemata
• The Complexity of the Finite Containment Problem for Petri Nets
• On Entailment
• A Decision Procedure For the System E_Ī of Entailment with Negation
• Counter machines and counter languages

This page was built for publication: The complexity of decision procedures in relevance logic II