Enumerating Independent Linear Inferences

DOI10.46298/LMCS-19(2:11)2023arXiv2111.05209MaRDI QIDQ6135760FDOQ6135760

Authors: Anupam Das 

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: A linear inference is a valid inequality of Boolean algebra in which each variable occurs at most once on each side. In this work we leverage recently developed graphical representations of linear formulae to build an implementation that is capable of more efficiently searching for switch-medial-independent inferences. We use it to find four `minimal' 8-variable independent inferences and also prove that no smaller ones exist; in contrast, a previous approach based directly on formulae reached computational limits already at 7 variables. Two of these new inferences derive some previously found independent linear inferences. The other two (which are dual) exhibit structure seemingly beyond the scope of previous approaches we are aware of; in particular, their existence contradicts a conjecture of Das and Strassburger. We were also able to identify 10 minimal 9-variable linear inferences independent of all the aforementioned inferences, comprising 5 dual pairs, and present applications of our implementation to recent `graph logics'.

Full work available at URL: https://arxiv.org/abs/2111.05209

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Algorithm 457: finding all cliques of an undirected graph
• Complement reducible graphs
• Introduction to computability logic
• Linear logic
• Extension without cut
• The relative efficiency of propositional proof systems
• A game semantics for linear logic
• Title not available (Why is that?)
• A Local System for Classical Logic
• A system of interaction and structure
• Normalisation Control in Deep Inference via Atomic Flows
• A Characterization of Medial as Rewriting Rule
• On linear rewriting systems for Boolean logic and some applications to proof theory
• Title not available (Why is that?)
• An Analytic Propositional Proof System on Graphs
• Rewriting with linear inferences in propositional logic
• On the relative proof complexity of deep inference via atomic flows
• No complete linear term rewriting system for propositional logic
• Logic beyond formulas: a proof system on graphs
• Title not available (Why is that?)
• Coherent interaction graphs
• New Minimal Linear Inferences in Boolean Logic Independent of Switch and Medial

Cited In (1)

• Inference of Uniquely Terminating EML

This page was built for publication: Enumerating Independent Linear Inferences

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