{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:24:12Z","timestamp":1760297052951},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2002,8,1]],"date-time":"2002-08-01T00:00:00Z","timestamp":1028160000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2002,8]]},"abstract":"<jats:title>Abstract.<\/jats:title>\n          <jats:p>\n            The synthesis problem for Petri nets consists in deciding constructively the existence of a Petri net with sequential state graph isomorphic to a given graph. If events are attached to locations, one may set as an additional requirement that the synthesised net should be distributable; i.e. such that events at different locations have no common input place, whence distributed conflicts are avoided. Distributable nets are easily implemented by finite families of automata (one per location) communicating with each other by asynchronous message passing. We show that the general Petri net synthesis problem and its distributed version may both be solved in time polynomial in the size of the given graph. We report on some preliminary experiments of Petri net synthesis applied to the distribution of reactive automata using the tool\n            <jats:bold>\n              <jats:italic>SYNET<\/jats:italic>\n            <\/jats:bold>\n            .\n          <\/jats:p>","DOI":"10.1007\/s001650200022","type":"journal-article","created":{"date-parts":[[2003,12,10]],"date-time":"2003-12-10T21:38:13Z","timestamp":1071092293000},"page":"447-470","source":"Crossref","is-referenced-by-count":38,"title":["Distributing Finite Automata Through Petri Net Synthesis"],"prefix":"10.1145","volume":"13","author":[{"given":"\u00c9ric","family":"Badouel","sequence":"first","affiliation":[{"name":"ENSP, BP 8390, Yaound\u00e9, Cameroun, , , , , , CM"}]},{"given":"Beno\u00eet","family":"Caillaud","sequence":"additional","affiliation":[{"name":"IRISA, Campus de Beaulieu, Rennes, France, , , , , , FR"}]},{"given":"P.","family":"Darondeau","sequence":"additional","affiliation":[{"name":"IRISA, Campus de Beaulieu, Rennes, France, , , , , , FR"}]}],"member":"320","reference":[{"key":"p_1","first-page":"647","article-title":"Polynomial algorithms for the synthesis of bounded nets. Proceedings Caap 95","volume":"915","author":"Badouel E.","year":"1995","journal-title":"Lecture Notes in Computer Science"},{"key":"p_2","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0304-3975(96)00219-8","article-title":"The synthesis problem for elementary net systems is NP-complete","volume":"186","author":"Badouel E.","year":"1997","journal-title":"Theoretical Computer Science"},{"key":"p_4","first-page":"11","volume-title":"Structures in Concurrency Theory","author":"Bernardinello L.","year":"1996"},{"key":"p_6","first-page":"9","article-title":"Bounded Petri-net synthesis techniques and their applications to the distribution of reactive automata","volume":"33","author":"Cai","year":"1999","journal-title":"European Journal of Automation"},{"key":"p_7","volume-title":"North-Holland","author":"Che","year":"1971"},{"key":"p_8","first-page":"164","volume-title":"Proceedings of ICCAD'95","author":"Cortadella J.","year":"1995"},{"issue":"8","key":"p_9","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1109\/12.707587","article-title":"Deriving Petri nets from finite transition systems","volume":"47","author":"Cortadella J.","year":"1998","journal-title":"IEEE Transactions on Computers"},{"key":"p_10","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1109\/ASYNC.1996.494436","volume-title":"Proceedings of the 2nd International Symposium on Advanced Research on Asynchronous Circuits and Systems","author":"Cortadella J.","year":"1996"},{"key":"p_11","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s002360050046","article-title":"The synthesis problem of Petri nets","volume":"33","author":"De","year":"1996","journal-title":"Acta Informatica"},{"key":"p_12","first-page":"69","volume-title":"Semantics of Programming Languages and Model Theory","author":"Dr","year":"1993"},{"key":"p_13","volume-title":"From Petri nets to automata with concurrency. Draft communicated to the authors","author":"Dr","year":"1996"},{"key":"p_14","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF00264611","article-title":"Partial (set) 2-structures. Part I: Basic notions and the representation problem","volume":"27","author":"Eh","year":"1990","journal-title":"Acta Informatica"},{"key":"p_15","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF00264612","article-title":"Partial (set) 2-structures. Part II: State spaces of concurrent systems","volume":"27","author":"Eh","year":"1990","journal-title":"Acta Informatica"},{"key":"p_16","first-page":"613","volume-title":"Proceedings of IFIP Congress","author":"van Glabbeek R. J.","year":"1989"},{"key":"p_17","volume-title":"Graphes et algorithmes. Eyrolles","author":"Go","year":"1979"},{"key":"p_19","first-page":"161","volume-title":"Advances in Petri Nets 1991","author":"Hop","year":"1991"},{"key":"p_20","volume-title":"Algebra","author":"Ma","year":"1967"},{"issue":"4","key":"p_21","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1142\/S0129054192000231","article-title":"Petri nets and step transition systems","volume":"3","author":"Muk","year":"1992","journal-title":"International Journal of Foundations of Computer Science"},{"key":"p_22","volume-title":"Petri Nets. eatcs Monographs on Theoretical Computer Science","author":"Rei","year":"1985"},{"key":"p_23","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/978-1-4615-4493-7_41","volume-title":"Discrete Event Systems: Analysis and Control","author":"Rezg N.","year":"2000"},{"key":"p_24","volume-title":"Theory of Linear and Integer Programming","author":"Sch","year":"1986"},{"key":"p_25","unstructured":"[Synet] http:\/\/www.irisa.fr\/pampa\/LOGICIELS\/synet\/synet.html"},{"issue":"3","key":"p_26","first-page":"391","article-title":"Test generation with inputs, outputs and repetitive quiescence","volume":"17","author":"Tre","year":"1996","journal-title":"Journal on Software: Concepts and Tools"},{"key":"p_27","first-page":"284","volume-title":"Proceedings of ICATPN'99","author":"Vog","year":"1999"},{"key":"p_28","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1023\/A:1008649930696","article-title":"Designing control logic for counterflow pipeline processor using Petri nets","volume":"12","author":"Yak","year":"1998","journal-title":"Formal Methods in System Design"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s001650200022.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s001650200022\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s001650200022","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T15:33:51Z","timestamp":1641483231000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s001650200022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,8]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2002,8]]}},"alternative-id":["10.1007\/s001650200022"],"URL":"https:\/\/doi.org\/10.1007\/s001650200022","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,8]]}}}