Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

On Negotiation as Concurrency Primitive II: Deterministic Cyclic Negotiations

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 8412))

Abstract

We continue our study of negotiations, a concurrency model with multi-party negotiation as primitive. In a previous paper [7] we have provided a correct and complete set of reduction rules for sound, acyclic, and (weakly) deterministic negotiations. In this paper we extend this result to all deterministic negotiations, including cyclic ones. We also show that this set of rules allows one to decide soundness and to summarize negotiations in polynomial time.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. van der Aalst, W.M.P.: The application of Petri nets to workflow management. J. Circuits, Syst. and Comput. 08(01), 21–66 (1998)

    Article  Google Scholar 

  2. Atdelzater, T., Atkins, E.M., Shin, K.G.: QoS negotiation in real-time systems and its application to automated flight control. IEEE Transactions on Computers 49(11), 1170–1183 (2000)

    Article  Google Scholar 

  3. Berthelot, G.: Transformations and decompositions of nets. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 254, pp. 359–376. Springer, Heidelberg (1987)

    Google Scholar 

  4. Chen, Y., Peng, Y., Finin, T., Labrou, Y., Cost, S., Chu, B., Sun, R., Wilhelm, B.: A negotiation-based multi-agent system for supply chain management. In: Proceedings of Agents 1999 Workshop on Agent Based Decision-Support for Managing the Internet-Enabled Supply-Chain, pp. 15–20 (1999)

    Google Scholar 

  5. Davis, R., Smith, R.G.: Negotiation as a metaphor for distributed problem solving. Artificial Intelligence 20(1), 63–109 (1983)

    Article  Google Scholar 

  6. Desel, J., Esparza, J.: Free choice Petri nets. Cambridge University Press, New York (1995)

    Book MATH  Google Scholar 

  7. Esparza, J., Desel, J.: On negotiation as concurrency primitive. In: D’Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013. LNCS, vol. 8052, pp. 440–454. Springer, Heidelberg (2013); (Extended version in arXiv:1307.2145)

    Google Scholar 

  8. Esparza, J., Desel, J.: On negotiation as concurrency primitive II: Deterministic cyclic negotiations. Technical report, Technische Universität München, Germany. Available via arxiv.org (2014)

    Google Scholar 

  9. Gastin, P., Petit, A., Zielonka, W.: An extension of Kleene’s and Ochmanski’s theorems to infinite traces. Theor. Comput. Sci. 125(2), 167–204 (1994)

    Article MATH MathSciNet  Google Scholar 

  10. Genest, B., Kuske, D., Muscholl, A.: A Kleene theorem and model checking algorithms for existentially bounded communicating automata. Inf. Comput. 204(6), 920–956 (2006)

    Article MATH MathSciNet  Google Scholar 

  11. Genrich, H.J., Thiagarajan, P.S.: A theory of bipolar synchronization schemes. Theor. Comput. Sci. 30, 241–318 (1984)

    Article MATH MathSciNet  Google Scholar 

  12. Haddad, S.: A reduction theory for coloured nets. In: Rozenberg, G. (ed.) APN 1989. LNCS, vol. 424, pp. 209–235. Springer, Heidelberg (1990)

    Chapter  Google Scholar 

  13. Haddad, S., Pradat-Peyre, J.-F.: New efficient Petri nets reductions for parallel programs verification. Parallel Processing Letters 16(1), 101–116 (2006)

    Article MathSciNet  Google Scholar 

  14. Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley Longman Publishing Co., Inc., Boston (2006)

    Google Scholar 

  15. Jennings, N.R., Faratin, P., Lomuscio, A.R., Parsons, S., Wooldridge, M.J., Sierra, C.: Automated negotiation: prospects, methods and challenges. Group Decision and Negotiation 10(2), 199–215 (2001)

    Article  Google Scholar 

  16. Simon, C.: Negotiation Processes – The Semantic Process Language and Applications. Shaker, Aachen (2008)

    Google Scholar 

  17. Winsborough, W.H., Seamons, K.E., Jones, V.E.: Automated trust negotiation. In: Proceedings of the DARPA Information Survivability Conference and Exposition, DISCEX 2000, vol. 1, pp. 88–102. IEEE (2000)

    Google Scholar 

  18. Xu, H., Shatz, S.M.: An agent-based Petri net model with application to seller/buyer design in electronic commerce. In: Proceedings of the 5th International Symposium on Autonomous Decentralized Systems, pp. 11–18. IEEE (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fakultät für Informatik, Technische Universität München, Germany

    Javier Esparza

  2. Fakultät für Mathematik und Informatik, FernUniversität in Hagen, Germany

    Jörg Desel

Authors
  1. Javier Esparza

    You can also search for this author inPubMed Google Scholar

  2. Jörg Desel

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. LaBRI, Universiy of Bordeaux, France

    Anca Muscholl

Rights and permissions

Copyright information

© 2014 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Esparza, J., Desel, J. (2014). On Negotiation as Concurrency Primitive II: Deterministic Cyclic Negotiations. In: Muscholl, A. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2014. Lecture Notes in Computer Science, vol 8412. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54830-7_17

Download citation

Publish with us


[8]ページ先頭

©2009-2025 Movatter.jp