Correctness of linear logic proof structures is NL-complete
type: Item
instance of: scholarly article
title: Correctness of linear logic proof structures is NL-complete
zbMATH Open document ID: 1222.03069
author: Paulin Jacobé de Naurois
author: Virgile Mogbil
published in: Theoretical Computer Science
publication date: 2011-05-10T00:00:00Z
Mathematics Subject Classification ID: 03F52
Mathematics Subject Classification ID: 03F07
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5886382
zbMATH Keywords: complexity classes
zbMATH Keywords: correctness criteria
zbMATH Keywords: linear logic
zbMATH Keywords: nondeterministic logspace
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.12.020
OpenAlex ID: W2092553770
cites work: Constant Depth Reducibility
cites work: The structure of multiplicatives
cites work: The additive multiboxes
cites work: Linear logic
cites work: Q4896506
cites work: Parsing MELL proof nets
cites work: Proof nets for unit-free multiplicative-additive linear logic
cites work: Nondeterministic Space is Closed under Complementation
cites work: New problems complete for nondeterministic log space
cites work: Q4842976
cites work: Q4650584
cites work: Fast verification of MLL proof nets via IMLL
cites work: Undirected ST-connectivity in log-space
cites work: Q3815544
DOI: 10.1016/J.TCS.2010.12.020
Recommended article: Correctness of Multiplicative (and Exponential) Proof Structures is NL-Complete
Recommended article: On \(\text{NP}\)-completeness in linear logic
Recommended article: Proofs as computations in linear logic
Recommended article: Q4244309
Recommended article: Correctness and Completeness of Logic Programs
Recommended article: Q4842970
Recommended article: Completeness for linear continuous logic
Recommended article: Compact Proof Certificates for Linear Logic
Recommended article: The semantics and proof theory of linear logic
Recommended article: Proof method of partial correctness and weak completeness for normal logic programs
description: scientific article; zbMATH DE number 5886382