The complexity of decision procedures in relevance logic II

DOI10.2307/2586811MaRDI QIDQ4948542zbMATH OpenOpenAlexFDO

Authors 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 bounddecision procedureAckermann functionlower bound on the complexityimplication-conjunction fragments

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1342215
• \(TW_+\) and \(RW_+\) are decidable
• scientific article; zbMATH DE number 2062375
• Constructive decision via redundancy-free proof-search

Cites work

• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 1489627 (Why is no real title available?)
• A Decision Procedure For the System E_Ī of Entailment with Negation
• Counter machines and counter languages
• Decision problems for propositional linear logic
• On Entailment
• Parallel program schemata
• Petri nets and large finite sets
• The Complexity of the Finite Containment Problem for Petri Nets

Cited in

(29)

• A decidable fragment of predicate calculus
• On the decidability of implicational ticket entailment
• An O(n n)-space decision procedure for the relevance logic B^+
• Non-primitive recursive decidability of products of modal logics with expanding domains
• Current trends in substructural logics
• Varieties of De Morgan monoids: minimality and irreducible algebras
• On the decision problem for MELL
• Constructive decision via redundancy-free proof-search
• The ideal view on Rackoff's coverability technique
• The Parametric Complexity of Lossy Counter Machines
• MOST SIMPLE EXTENSIONS OF ARE UNDECIDABLE
• Implicational relevance logic is 2-\textsc{ExpTime}-complete
• The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
• scientific article; zbMATH DE number 1420859 (Why is no real title available?)
• scientific article; zbMATH DE number 2062375 (Why is no real title available?)
• scientific article; zbMATH DE number 4012564 (Why is no real title available?)
• The decidability of a fragment of \(\text{BB}'\text{IW}\)-logic
• Relevance logic: problems open and closed
• Decision procedure of some relevant logics: a constructive perspective
• Branching in well-structured transition systems (invited talk)
• A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets
• scientific article; zbMATH DE number 3887654 (Why is no real title available?)
• scientific article; zbMATH DE number 54580 (Why is no real title available?)
• A Logical Autobiography
• scientific article; zbMATH DE number 1984514 (Why is no real title available?)
• A decision procedure revisited: Notes on direct logic, linear logic and its implementation
• On the termination and structural termination problems for counter machines with incrementing errors
• Tight length theorems for multiset extensions of Higman's lemma
• Complexity hierarchies beyond elementary

Describes a project that uses

Uses Software

• KRIPKE

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4948542)