{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T00:24:06Z","timestamp":1778804646591,"version":"3.51.4"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4s","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Digiteo"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>Join-Free Petri nets, whose transitions have at most one input place, model systems without synchronizations, while Choice-Free Petri nets, whose places have at most one output transition, model systems without conflicts. These classes respectively encompass the state machines (S-systems) and the marked graphs (T-systems).<\/jats:p>\n          <jats:p>\n            Whereas a structurally bounded and structurally live Petri net is said to be \u201cwell-formed\u201d, a bounded and live Petri net is said to be \u201cwell-behaved\u201d. Necessary and sufficient conditions for the well-formedness of Join-Free and Choice-Free nets have been known for some time, yet the behavioral properties of these classes are still not well understood. In particular\n            <jats:italic>polynomial<\/jats:italic>\n            sufficient conditions for liveness, that is, polynomial in time and with a polynomial initial number of tokens, have not been found until now. Besides,\n            <jats:italic>home markings<\/jats:italic>\n            , which can be reached from every reachable marking thus allowing for the construction of systems that can return to their initial data distribution, are not well apprehended either for these subclasses.\n          <\/jats:p>\n          <jats:p>\n            We extend results on weighted T-systems to the class of weighted Petri nets and present transformations which preserve the language of the system and reduce the initial marking. We introduce a notion of\n            <jats:italic>balancing<\/jats:italic>\n            that makes possible the transformation of conservative systems into so-called \u201ctoken-conservative\u201d systems, whose number of tokens is invariant, while retaining the feasible transition sequences. This transformation is pertinent for all well-formed Petri nets and leads to polynomial sufficient conditions of liveness for well-formed Join-Free and Choice-Free nets. Finally, we also provide polynomial live and home markings for Fork-Attribution systems.\n          <\/jats:p>","DOI":"10.1145\/2627349","type":"journal-article","created":{"date-parts":[[2014,11,18]],"date-time":"2014-11-18T13:49:53Z","timestamp":1416318593000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Polynomial Sufficient Conditions of Well-Behavedness and Home Markings in Subclasses of Weighted Petri Nets"],"prefix":"10.1145","volume":"13","author":[{"given":"Thomas","family":"Hujsa","sequence":"first","affiliation":[{"name":"LIP6, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Marc","family":"Delosme","sequence":"additional","affiliation":[{"name":"IBISC, Evry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alix","family":"Munier-Kordon","sequence":"additional","affiliation":[{"name":"LIP6, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.09.030"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1016\/S0016-0032(99)00008-3","volume-title":"Structure theory of choice-free Petri nets based on eigenvalues","author":"Amer-Yahia Ch\u00e9rif","year":"1999"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/3468.747851"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/647739.735652"},{"key":"e_1_2_1_5_1","series-title":"Lecture Notes in Computer Science","volume-title":"Application and Theory of Petri Nets","author":"Barkaoui Kamel","year":"1996"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/44.2.124"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2013.12"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/207572"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 20th Asilomar Conference on Signals, Systems and Computers. 503--507","author":"Engels Marc"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2379396.2379398"},{"key":"e_1_2_1_11_1","volume-title":"Lectures on Petri Nets I: Basic Models","author":"Esparza Javier"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00409-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00359-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90014-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.07.037"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2826"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CCOL0521340446.006"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Linear algebra in net theory","author":"Memmi G\u00e9rard"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.24143"},{"key":"e_1_2_1_21_1","volume-title":"Structures in Concurrency Theory","author":"Recalde Laura"},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","volume-title":"Application and Theory of Petri Nets","author":"Recalde Laura","year":"1996"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.681245"},{"key":"e_1_2_1_24_1","volume-title":"Mathematical Foundations of Computer Science","author":"Sifakis Joseph"},{"key":"e_1_2_1_25_1","volume-title":"Lectures on Petri Nets I: Basic Models","author":"Silva Manuel"},{"key":"e_1_2_1_26_1","series-title":"Lecture Notes in Computer Science","volume-title":"Jos\u00e9 Manuel Colom, and Manuel Silva","author":"Teruel Enrique","year":"1992"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/3468.553226"},{"key":"e_1_2_1_28_1","series-title":"Lecture Notes in Computer Science","volume-title":"Application and Theory of Petri Nets","author":"Teruel Enrique","year":"1993"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00124-7"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278647"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2627349","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2627349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:08Z","timestamp":1750229768000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2627349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":30,"journal-issue":{"issue":"4s","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2627349"],"URL":"https:\/\/doi.org\/10.1145\/2627349","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}