{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:45:24Z","timestamp":1743061524317,"version":"3.40.3"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030452308"},{"type":"electronic","value":"9783030452315"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Negotiations were introduced in\u00a0[6] as a model for concurrent systems with multiparty decisions. What is very appealing with negotiations is that it is one of the very few non-trivial concurrent models where several interesting problems, such as soundness, i.e. absence of deadlocks, can be solved in PTIME [3]. In this paper, we introduce the model of timed negotiations and consider the problem of computing the minimum and the maximum execution times of a negotiation. The latter can be solved using the algorithm of [10] computing costs in negotiations, but surprisingly minimum execution time cannot.<\/jats:p><jats:p>This paper proposes new algorithms to compute both minimum and maximum execution time, that work in much more general classes of negotiations than [10], that only considered sound and deterministic negotiations. Further, we uncover the precise complexities of these questions, ranging from PTIME to<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varDelta _2^P$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msubsup><mml:mi>\u0394<\/mml:mi><mml:mn>2<\/mml:mn><mml:mi>P<\/mml:mi><\/mml:msubsup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete. In particular, we show that computing the minimum execution time is more complex than computing the maximum execution time in most classes of negotiations we consider.<\/jats:p>","DOI":"10.1007\/978-3-030-45231-5_3","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T10:02:53Z","timestamp":1587117773000},"page":"37-56","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Timed Negotiations"],"prefix":"10.1007","author":[{"given":"S.","family":"Akshay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Blaise","family":"Genest","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lo\u00efc","family":"H\u00e9lou\u00ebt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharvik","family":"Mital","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"S. Akshay, B. Genest, L. H\u00e9lou\u00ebt, and S. Mital. Timed negotiations (extended version). In Research report, https:\/\/hal.inria.fr\/hal-02337887, 2020.","DOI":"10.1007\/978-3-030-45231-5_3"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"J. Desel. Reduction and design of well-behaved concurrent systems. In CONCUR \u201990, Theories of Concurrency: Unification and Extension, Amsterdam, The Netherlands, August 27-30, 1990, Proceedings, volume 458 of Lecture Notes in Computer Science, pages 166\u2013181. Springer, 1990.","DOI":"10.1007\/BFb0039059"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"J. Desel, J. Esparza, and P. Hoffmann. Negotiation as concurrency primitive. Acta Inf. 56(2):93\u2013159, 2019.","DOI":"10.1007\/s00236-018-0318-9"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"J. Esparza. Decidability and complexity of petri net problems - an introduction. In Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Dagstuhl, September 1996, volume 1491 of Lecture Notes in Computer Science, pages 374\u2013428. Springer, 1998.","DOI":"10.1007\/3-540-65306-6_20"},{"key":"3_CR5","unstructured":"J. Esparza and J. Desel. Free Choice Petri Nets. Cambridge University Press, 1995."},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"J. Esparza and J. Desel. On negotiation as concurrency primitive. In CONCUR 2013 - Concurrency Theory - 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings, volume 8052 of Lecture Notes in Computer Science, pages 440\u2013454. Springer, 2013.","DOI":"10.1007\/978-3-642-40184-8_31"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"J. Esparza and J. Desel. On negotiation as concurrency primitive II: deterministic cyclic negotiations. In FOSSACS\u201914, volume 8412 of Lecture Notes in Computer Science, pages 258\u2013273. Springer, 2014.","DOI":"10.1007\/978-3-642-54830-7_17"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"J. Esparza and P. Hoffmann. Reduction rules for colored workflow nets. In Fundamental Approaches to Software Engineering - 19th International Conference, FASE 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceedings, volume 9633 of Lecture Notes in Computer Science, pages 342\u2013358. Springer, 2016","DOI":"10.1007\/978-3-662-49665-7_20"},{"key":"3_CR9","unstructured":"J. Esparza, D. Kuperberg, A. Muscholl, and I. Walukiewicz. Soundness in negotiations. Logical Methods in Computer Science, 14(1), 2018."},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"J. Esparza, A. Muscholl, and I. Walukiewicz. Static analysis of deterministic negotiations. In 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1\u201312, 2017.","DOI":"10.1109\/LICS.2017.8005144"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"S. Haddad. A reduction theory for coloured nets. In Advances in Petri Nets 1989, volume 424 of Lecture Notes in Computer Science, pages 209\u2013235. Springer, 1990.","DOI":"10.1007\/3-540-52494-0_31"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"P. Hoffmann. Negotiation games. In Javier Esparza and Enrico Tronci, editors, Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2015, Genoa, Italy, 21-22nd September 2015., volume 193 of EPTCS, pages 31\u201342, 2015.","DOI":"10.4204\/EPTCS.193.0"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"M. W. Krentel. The complexity of optimization problems. Journal of computer and system sciences 36(3):490\u2013509, 1988.","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"3_CR14","unstructured":"P.M. Merlin. A Study of the Recoverability of Computing Systems. PhD thesis, University of California, Irvine, CA, USA, 1974."},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC \u201982, pages 255\u2013260, New York, NY, USA, 1982. ACM","DOI":"10.1145\/800070.802199"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"R.H. Sloan and U.A. Buy. Reduction rules for time petri nets. Acta Inf., 33(7):687\u2013706, 1996.","DOI":"10.1007\/s002360050066"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45231-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:47:14Z","timestamp":1666367234000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45231-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030452308","9783030452315"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45231-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dublin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ireland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 April 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2020\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"98","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference could not take place due to the COVID-19 pandemic. There was an online event on July 2, 2020.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}