Linear constraint systems as high-level nets

Eike Best; Catuscia Palamidessi

doi:10.1007/3-540-61604-7_72

Linear constraint systems as high-level nets

Eike Best
, Catuscia Palamidessi

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Linear constraint systems are simple deductive systems based on the main underlying idea of linear logic: hypotheses represent physical resources which are consumed by the entailment relation. For such systems, we define back-and-forth translations into a class of high-level Petri nets. Using the specific properties of that class of nets, and previous results about the complexity of the reachability problem for such nets, we examine the complexity of the entailment problem for finitely generated linear constraint systems and we show that it is NP-complete.

Original language	English
Title of host publication	CONCUR 1996
Subtitle of host publication	Concurrency Theory - 7th International Conference, Proceedings
Editors	Ugo Montanari, Vladimiro Sassone
Publisher	Springer Verlag
Pages	498-513
Number of pages	16
ISBN (Print)	9783540616047
DOIs	https://doi.org/10.1007/3-540-61604-7_72
Publication status	Published - 1 Jan 1996
Externally published	Yes
Event	7th International Conference on Concurrency Theory, CONCUR 1996 - Pisa, Italy Duration: 26 Aug 1996 → 29 Aug 1996

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1119
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Concurrency Theory, CONCUR 1996
Country/Territory	Italy
City	Pisa
Period	26/08/96 → 29/08/96

Access to Document

10.1007/3-540-61604-7_72

Cite this

Best, E., & Palamidessi, C. (1996). Linear constraint systems as high-level nets. In U. Montanari, & V. Sassone (Eds.), CONCUR 1996: Concurrency Theory - 7th International Conference, Proceedings (pp. 498-513). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1119). Springer Verlag. https://doi.org/10.1007/3-540-61604-7_72

Best, Eike ; Palamidessi, Catuscia. / Linear constraint systems as high-level nets. CONCUR 1996: Concurrency Theory - 7th International Conference, Proceedings. editor / Ugo Montanari ; Vladimiro Sassone. Springer Verlag, 1996. pp. 498-513 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4c98239fa1594e8db2cf8eacb817c499,

title = "Linear constraint systems as high-level nets",

abstract = "Linear constraint systems are simple deductive systems based on the main underlying idea of linear logic: hypotheses represent physical resources which are consumed by the entailment relation. For such systems, we define back-and-forth translations into a class of high-level Petri nets. Using the specific properties of that class of nets, and previous results about the complexity of the reachability problem for such nets, we examine the complexity of the entailment problem for finitely generated linear constraint systems and we show that it is NP-complete.",

author = "Eike Best and Catuscia Palamidessi",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1996.; 7th International Conference on Concurrency Theory, CONCUR 1996 ; Conference date: 26-08-1996 Through 29-08-1996",

year = "1996",

month = jan,

day = "1",

doi = "10.1007/3-540-61604-7\_72",

language = "English",

isbn = "9783540616047",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "498--513",

editor = "Ugo Montanari and Vladimiro Sassone",

booktitle = "CONCUR 1996",

}

Best, E & Palamidessi, C 1996, Linear constraint systems as high-level nets. in U Montanari & V Sassone (eds), CONCUR 1996: Concurrency Theory - 7th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1119, Springer Verlag, pp. 498-513, 7th International Conference on Concurrency Theory, CONCUR 1996, Pisa, Italy, 26/08/96. https://doi.org/10.1007/3-540-61604-7_72

Linear constraint systems as high-level nets. / Best, Eike; Palamidessi, Catuscia.
CONCUR 1996: Concurrency Theory - 7th International Conference, Proceedings. ed. / Ugo Montanari; Vladimiro Sassone. Springer Verlag, 1996. p. 498-513 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1119).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Linear constraint systems as high-level nets

AU - Best, Eike

AU - Palamidessi, Catuscia

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1996.

PY - 1996/1/1

Y1 - 1996/1/1

N2 - Linear constraint systems are simple deductive systems based on the main underlying idea of linear logic: hypotheses represent physical resources which are consumed by the entailment relation. For such systems, we define back-and-forth translations into a class of high-level Petri nets. Using the specific properties of that class of nets, and previous results about the complexity of the reachability problem for such nets, we examine the complexity of the entailment problem for finitely generated linear constraint systems and we show that it is NP-complete.

AB - Linear constraint systems are simple deductive systems based on the main underlying idea of linear logic: hypotheses represent physical resources which are consumed by the entailment relation. For such systems, we define back-and-forth translations into a class of high-level Petri nets. Using the specific properties of that class of nets, and previous results about the complexity of the reachability problem for such nets, we examine the complexity of the entailment problem for finitely generated linear constraint systems and we show that it is NP-complete.

U2 - 10.1007/3-540-61604-7_72

DO - 10.1007/3-540-61604-7_72

M3 - Conference contribution

AN - SCOPUS:84955608992

SN - 9783540616047

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 498

EP - 513

BT - CONCUR 1996

A2 - Montanari, Ugo

A2 - Sassone, Vladimiro

PB - Springer Verlag

T2 - 7th International Conference on Concurrency Theory, CONCUR 1996

Y2 - 26 August 1996 through 29 August 1996

ER -

Best E, Palamidessi C. Linear constraint systems as high-level nets. In Montanari U, Sassone V, editors, CONCUR 1996: Concurrency Theory - 7th International Conference, Proceedings. Springer Verlag. 1996. p. 498-513. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-61604-7_72

Linear constraint systems as high-level nets

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this