DocumentCode :
2038926
Title :
Correctness of Multiplicative Additive Proof Structures is NL-Complete
Author :
de Naurois, P.J. ; Mogbil, Virgile
Author_Institution :
Inst. Galilee, Lab. d´´Inf., Univ. Paris Nord, Villetaneuse
fYear :
2008
fDate :
24-27 June 2008
Firstpage :
476
Lastpage :
485
Abstract :
The authors revisit the correctness criterion for the multiplicative additive fragment of linear logic. We prove that deciding the correctness of corresponding proof structures is NL-complete.
Keywords :
formal logic; theorem proving; NL-complete; linear logic; multiplicative additive proof structures; Additives; Calculus; Complexity theory; Computer science; Jacobian matrices; Logic; Parallel algorithms; Computational Complexity; Correctness Criterion; Multiplicative Additive Linear Logic; NL-completness; proof-nets;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science, 2008. LICS '08. 23rd Annual IEEE Symposium on
Conference_Location :
Pittsburgh, PA
ISSN :
1043-6871
Print_ISBN :
978-0-7695-3183-0
Type :
conf
DOI :
10.1109/LICS.2008.20
Filename :
4557936
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2038926
بازگشت