A System of Interaction and Structure III: The Complexity of BV and Pomset Logic

DOI10.46298/LMCS-19(4:25)2023arXiv2209.07825OpenAlexW4312076504MaRDI QIDQ6137849

Lê Thành Dũng Nguyên, Lutz Straßburger

Publication date: 16 January 2024

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

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

zbMATH Keywords

cographsproof netsdeep inferenceseries-parallel ordersrelation websdicographsPomset logicsystem \textsf{BV}

Mathematics Subject Classification ID

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

Cites Work

• Visible acyclic differential nets. I: Semantics
• The logic of categorial grammars. A deductive account of natural language syntax and semantics
• Deep inference and probabilistic coherence spaces
• Linear logic
• Extension without cut
• Complement reducible graphs
• Complete sets and the polynomial-time hierarchy
• The structure of multiplicatives
• A term equality problem equivalent to graph isomorphism
• Handsome proof-nets: Perfect matchings and cographs
• Simple free star-autonomous categories and full coherence
• Complexity of trails, paths and circuits in arc-colored digraphs
• Non-commutative logic. I: The multiplicative fragment
• System BV is NP-complete
• Fully dynamic recognition algorithm and certificate for directed cographs
• A system of interaction and structure IV
• A Local System for Classical Logic
• A system of interaction and structure V: the exponentials and splitting
• A correspondence between rooted planar maps and normal planar lambda terms
• The Mathematics of Sentence Structure
• Quantales and (noncommutative) linear logic
• A Characterization of Hypercoherent Semantic Correctness in Multiplicative Additive Linear Logic
• Acyclicity and Coherence in Multiplicative Exponential Linear Logic
• The Recognition of Series Parallel Digraphs
• The relative efficiency of propositional proof systems
• The Logic of Bunched Implications
• The mix rule
• A semantic characterisation of the correctness of a proof net
• Non-commutative logic II: sequent calculus and phase semantics
• A complete axiomatisation for the inclusion of series-parallel partial orders
• Classes of Directed Graphs
• The Consistency and Complexity of Multiplicative Additive System Virtual
• Linear logic model of state revisited
• System NEL is Undecidable
• De Morgan Dual Nominal Quantifiers Modelling Private Names in Non-Commutative Logic
• On noncommutative extensions of linear logic
• Pomset Logic
• An Analytic Propositional Proof System on Graphs
• Ribbon Tensorial Logic
• Logic Beyond Formulas
• Constructing weak simulations from linear implications for processes with private names
• A system of interaction and structure
• A System of Interaction and Structure II: The Need for Deep Inference
• Computer Science Logic
• Computational Complexity
• Proof nets for multiplicative cyclic linear logic and Lambek calculus
• Computer Science Logic
• A Logical Basis for Quantum Evolution and Entanglement
• Temperley-Lieb Algebra: From Knot Theory to Logic and Computation via Quantum Mechanics
• A deep inference system with a self-dual binder which is complete for linear lambda calculus
• Generalized connectives for multiplicative linear logic
• BV and Pomset Logic Are Not the Same
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A System of Interaction and Structure III: The Complexity of BV and Pomset Logic