{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:08:14Z","timestamp":1753888094074},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540505808"},{"type":"electronic","value":"9783540460596"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-50580-6_30","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:27:40Z","timestamp":1330183660000},"page":"200-226","source":"Crossref","is-referenced-by-count":13,"title":["On questions of fairness and temporal logic for conflict-free Petri nets"],"prefix":"10.1007","author":[{"given":"Rodney R.","family":"Howell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louis E.","family":"Rosier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0020-0190(86)90071-2","volume":"22","author":"K. Apt","year":"1986","unstructured":"Apt, K. and Kozen, D., Limits for Automatic Verification of Finite-State Concurrent Systems, Information Processing Letters 22 (1986), 307\u2013310.","journal-title":"Information Processing Letters"},{"key":"10_CR2","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(84)90114-5","volume":"18","author":"E. Best","year":"1984","unstructured":"Best, E., Fairness and Conspiracies, Information Processing Letters 18 (1984), 215\u2013220. Addendum Vol. 19, page 162, 1984.","journal-title":"Information Processing Letters"},{"issue":"2","key":"10_CR3","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1090\/S0002-9939-1976-0396605-3","volume":"55","author":"I. Borosh","year":"1976","unstructured":"Borosh, I. and Treybig, L., Bounds on Positive Integral Solutions of Linear Diophantine Equations, Proc. AMS 55, 2 (March 1976), 299\u2013304.","journal-title":"Proc. AMS"},{"key":"10_CR4","unstructured":"Brams, G., Reseaux de Petri: Theorie et Pratique \u2014 Tome 1: Theorie et Analyse, (Masson, Paris, 1983)."},{"key":"10_CR5","first-page":"396","volume":"247","author":"H. Carstensen","year":"1987","unstructured":"Carstensen, H., Decidability Questions for Fairness in Petri Nets, Proceedings of the 4th Symposium on Theoretical Aspects of Computer Science, LNCS 247 (1987), 396\u2013407.","journal-title":"Proceedings of the 4th Symposium on Theoretical Aspects of Computer Science"},{"key":"10_CR6","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/3-540-15204-0_6","volume-title":"Advances in Petri Nets 1984","author":"H. Carstensen","year":"1985","unstructured":"Carstensen, H. and Valk, R., Infinite Behaviour and Fairness in Petri Nets, in: Rozenberg, G., Ed., Advances in Petri Nets 1984; LNCS 188, (Springer, Berlin, 1985), pp. 83\u2013100."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Clarke, E., Gr\u00fcmberg, O., and Browne, M., Reasoning about Networks with Many Identical Finite-State Processes, Proceedings of the 5th Symposium on Principles of Distributed Computing (1986), 240\u2013248.","DOI":"10.1145\/10590.10611"},{"issue":"3","key":"10_CR8","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0020-0190(75)90020-4","volume":"3","author":"S. Crespi-Reghizzi","year":"1975","unstructured":"Crespi-Reghizzi, S. and Mandrioli, D., A Decidability Theorem for a Class of Vector Addition Systems, Information Processing Letters, 3 3 (1975), 78\u201380.","journal-title":"Information Processing Letters"},{"key":"10_CR9","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0167-6423(87)90036-0","volume":"8","author":"E. Emerson","year":"1987","unstructured":"Emerson, E. and Lei, C., Modalities for Model Checking: Branching Time Logic Strikes Back, Science of Computer Programming 8 (1987), 275\u2013306.","journal-title":"Science of Computer Programming"},{"key":"10_CR10","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0022-0000(80)90009-4","volume":"20","author":"A. Ginzburg","year":"1980","unstructured":"Ginzburg, A. and Yoeli, M., Vector Addition Systems and Regular Languages, J. of Computer and System Sciences 20 (1980), 277\u2013284.","journal-title":"J. of Computer and System Sciences"},{"issue":"1","key":"10_CR11","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(80)90026-5","volume":"11","author":"J. Grabowski","year":"1980","unstructured":"Grabowski, J., The Decidability of Persistence for Vector Addition Systems, Information Processing Letters 11, 1 (1980), 20\u201323.","journal-title":"Information Processing Letters"},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1145\/2166.357214","volume":"5","author":"S. Hart","year":"1983","unstructured":"Hart, S., Sharir, M., and Pnueli, A., Termination of Probabilistic Concurrent Programs, ACM Transactions on Programming Languages and Systems 5 (1983), 356\u2013380.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"10_CR13","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0304-3975(79)90041-0","volume":"8","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J. and Pansiot, J., On the Reachability Problem for 5-Dimensional Vector Addition Systems, Theoret. Comp. Sci. 8 (1979), 135\u2013159.","journal-title":"Theoret. Comp. Sci."},{"key":"10_CR14","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0304-3975(86)90026-5","volume":"46","author":"R. Howell","year":"1986","unstructured":"Howell, R., Rosier, L., Huynh, D., and Yen, H., Some Complexity Bounds for Problems Concerning Finite and 2-Dimensional Vector Addition Systems with States, Theoret. Comp. Sci. 46 (1986), 107\u2013140.","journal-title":"Theoret. Comp. Sci."},{"key":"10_CR15","first-page":"509","volume":"267","author":"R. Howell","year":"1987","unstructured":"Howell, R., and Rosier, L., Completeness Results for Reachability, Containment, and Equivalence with Respect to Conflict-Free Vector Replacement Systems, Proc. of the 14th International Colloquium on Automata, Languages, and Programming, LNCS 267 (1987), 509\u2013520. To appear in J. of Computer and System Sciences.","journal-title":"Proc. of the 14th International Colloquium on Automata, Languages, and Programming"},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(87)90089-5","volume":"25","author":"R. Howell","year":"1987","unstructured":"Howell, R., Rosier, L., and Yen, H., An O(n1.5) Algorithm to Decide Boundedness for Conflict-Free Vector Replacement Systems, Information Processing Letters 25 (1987), 27\u201333.","journal-title":"Information Processing Letters"},{"key":"10_CR17","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"Jones, N., Space-Bounded Reducibility Among Combinatorial Problems, J. of Computer and System Sciences 11 (1975), 68\u201375.","journal-title":"J. of Computer and System Sciences"},{"key":"10_CR18","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(77)90014-7","volume":"4","author":"N. Jones","year":"1977","unstructured":"Jones, N., Landweber, L. and Lien, Y., Complexity of Some Problems in Petri Nets, Theoret. Comp. Sci. 4 (1977), 277\u2013299.","journal-title":"Theoret. Comp. Sci."},{"issue":"2","key":"10_CR19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0022-0000(69)80011-5","volume":"3","author":"R. Karp","year":"1969","unstructured":"Karp, R. and Miller, R., Parallel Program Schemata, J. of Computer and System Sciences 3, 2 (1969), 147\u2013195.","journal-title":"J. of Computer and System Sciences"},{"key":"10_CR20","unstructured":"Keller, R.M., Vector Replacement Systems: A Formalism for Modelling Asynchronous Systems, TR 117, (Princeton University, CSL, 1972)."},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Kosaraju, R., Decidability of Reachability in Vector Addition Systems, Proceedings of the 14th Annual ACM Symposium on Theory of Computing (1982), 267\u2013280.","DOI":"10.1145\/800070.802201"},{"key":"10_CR22","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/BF01691063","volume":"3","author":"L. Landweber","year":"1969","unstructured":"Landweber, L., Decision Problems for \u03c9-Automata, Math. Syst. Theory 3 (1969), 376\u2013384.","journal-title":"Math. Syst. Theory"},{"issue":"3","key":"10_CR23","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1145\/322077.322079","volume":"25","author":"L. Landweber","year":"1978","unstructured":"Landweber, L. and Robertson, E., Properties of Conflict-Free and Persistent Petri Nets, JACM 25, 3 (1978), 352\u2013364.","journal-title":"JACM"},{"key":"10_CR24","first-page":"264","volume":"115","author":"D. Lehman","year":"1981","unstructured":"Lehman, D., Pnueli, A., and Stavi, J., Impartiality, Justice, and Fairness: The Ethics of Concurrent Termination, Proceedings of the 8th International Colloquium on Automata, Languages, and Programming, LNCS 115 (1981), 264\u2013277.","journal-title":"Proceedings of the 8th International Colloquium on Automata, Languages, and Programming"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Lichtenstein, O., and Pnueli, A., Checking that Finite State Concurrent Programs Satisfy their Linear Specification, Proceedings of the 12th Annual ACM Symposium on Principles of Programming Languages (1985), 97\u2013107.","DOI":"10.1145\/318593.318622"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Lichtenstein, O., Pneuli, A., and Zuck, L., The Glory of the Past, Proceedings of the Workshop on Logics of Programs (1985), 196\u2013218.","DOI":"10.1007\/3-540-15648-8_16"},{"key":"10_CR27","first-page":"385","volume":"71","author":"Z. Manna","year":"1979","unstructured":"Manna, Z., and Pnueli, A., The Modal Logic of Programs, Proceedings of the 6th International Colloquium on Automata, Languages, and Programming, LNCS 71 (1979), 385\u2013410.","journal-title":"LNCS"},{"issue":"3","key":"10_CR28","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"E. Mayr","year":"1984","unstructured":"Mayr, E., An Algorithm for the General Petri Net Reachability Problem, SIAM J. Comput. 13, 3 (1984), 441\u2013460. A preliminary version of this paper was presented at the 13th Annual Symposium on Theory of Computing, 1981.","journal-title":"SIAM J. Comput."},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF00289268","volume":"15","author":"E. Mayr","year":"1981","unstructured":"Mayr, E., Persistence of Vector Replacement Systems is Decidable, Acta Informatica 15 (1981), 309\u2013318.","journal-title":"Acta Informatica"},{"key":"10_CR30","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M. Minsky","year":"1961","unstructured":"Minsky, M., Recursive Unsolvability of Post's Problem of \u2018Tag\u2019 and Other Topics in the Theory of Turing Machines, Annals of Mathematics 74 (1961), 437\u2013455.","journal-title":"Annals of Mathematics"},{"key":"10_CR31","unstructured":"M\u00fcller, H., On the Reachability Problem for Persistent Vector Replacement Systems, Computing, Suppl. 3 (1981), 89\u2013104."},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/357172.357178","volume":"4","author":"S. Owicki","year":"1982","unstructured":"Owicki, S., and Lamport, L., Proving Liveness Properties of Concurrent Programs, ACM Trans. on Programming Languages and Syst. 4 (1982), 455\u2013495.","journal-title":"ACM Trans. on Programming Languages and Syst."},{"key":"10_CR33","volume-title":"Petri Net Theory and the Modeling of Systems","author":"J. Peterson","year":"1981","unstructured":"Peterson, J., Petri Net Theory and the Modeling of Systems, (Prentice Hall, Englewood Cliffs, NJ, 1981)."},{"key":"10_CR34","unstructured":"Pnueli, A., and Koren, T., There Exist Decidable Context-Free Propositional Dynamic Logics, CMU Workshop on Logics of Programs, LNCS 164, (1983)."},{"key":"10_CR35","doi-asserted-by":"crossref","unstructured":"Pnueli, A., The Temporal Logic of Programs, Proceedings of the 19th Annual Symposium on Foundations of Computer Science (1977).","DOI":"10.1109\/SFCS.1977.32"},{"key":"10_CR36","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF00265555","volume":"19","author":"J. Queille","year":"1983","unstructured":"Queille, J., and Sifakis, J., Fairness and Related Properties in Transition Systems\u2014A Temporal Logic to Deal with Fairness, Acta Informatica 19 (1983), 195\u2013220.","journal-title":"Acta Informatica"},{"key":"10_CR37","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1137\/0216052","volume":"16","author":"L. Rosier","year":"1987","unstructured":"Rosier, L. and Yen, H., Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning \u03c9-Machines, SIAM J. Comput. 16 (1987), 779\u2013807.","journal-title":"SIAM J. Comput."},{"key":"10_CR38","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/3-540-16761-7_83","volume":"226","author":"L. Rosier","year":"1986","unstructured":"Rosier, L. and Yen, H., On the Complexity of Deciding Fair Termination of Probabilistic Concurrent Finite-State Programs, Proceedings of the 13th International Colloquium on Automata, Languages and Programming, LNCS 226 (1986), 334\u2013343. To appear in Theoret. Comp. Sci..","journal-title":"Proceedings of the 13th International Colloquium on Automata, Languages and Programming"},{"key":"10_CR39","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1145\/3828.3837","volume":"32","author":"A. Sistla","year":"1985","unstructured":"Sistla, A., and Clarke, E., The Complexity of Propositional Linear Temporal Logic, JACM 32 (1985), 733\u2013749.","journal-title":"JACM"},{"key":"10_CR40","unstructured":"Suzuki, I., Fundamental Properties and Applications of Temporal Petri Nets, Proceedings of the 19th Annual Conference on Information Sciences and Systems, The Johns Hopkins University (1985), 641\u2013646."},{"key":"10_CR41","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. Tarjan","year":"1972","unstructured":"Tarjan, R., Depth First Search and Linear Graph Algorithms, SIAM J. Comput. 1 (1972), 146\u2013160.","journal-title":"SIAM J. Comput."},{"key":"10_CR42","first-page":"377","volume":"254","author":"R. Valk","year":"1987","unstructured":"Valk, R., Infinite Behaviour and Fairness, Proc. Advanced Course on Petri Nets, 1986, LNCS 254 (1987), 377\u2013396.","journal-title":"Proc. Advanced Course on Petri Nets, 1986"},{"key":"10_CR43","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(81)90067-2","volume":"23","author":"R. Valk","year":"1981","unstructured":"Valk, R. and Vidal-Naquet, G., Petri Nets and Regular Languages, J. of Computer and System Sciences 23 (1981), 299\u2013325.","journal-title":"J. of Computer and System Sciences"},{"key":"10_CR44","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/BF00289715","volume":"21","author":"R. Valk","year":"1985","unstructured":"Valk, R., and Jantzen, M., The Residue of Vector Sets with Applications to Decidability Problems in Petri Nets, Acta Informatica 21 (1985), 643\u2013674.","journal-title":"Acta Informatica"},{"key":"10_CR45","doi-asserted-by":"crossref","unstructured":"Vardi, M., Automatic Verification of Probablistic Concurrent Finite-State Programs, Proceedings of the 26th Annual Symposium on Foundations of Computer Science (1985), 327\u2013338.","DOI":"10.1109\/SFCS.1985.12"},{"issue":"3","key":"10_CR46","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/0020-0190(81)90117-4","volume":"13","author":"H. Yamasaki","year":"1981","unstructured":"Yamasaki, H., On Weak Persistency of Petri Nets, Information Processing Letters 13, 3 (1981), 94\u201397.","journal-title":"Information Processing Letters"},{"key":"10_CR47","volume-title":"Past Temporal Logic","author":"L. Zuck","year":"1986","unstructured":"Zuck, L., Past Temporal Logic, Ph.D. Thesis, The Weizmann Institute of Science, Rehovot, Isreal, August, 1986."}],"container-title":["Lecture Notes in Computer Science","Advances in Petri Nets 1988"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50580-6_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:18:30Z","timestamp":1605629910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50580-6_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540505808","9783540460596"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/3-540-50580-6_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}