{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:20Z","timestamp":1763468000022},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153488"},{"type":"electronic","value":"9783642153495"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15349-5_4","type":"book-chapter","created":{"date-parts":[[2010,8,20]],"date-time":"2010-08-20T23:39:27Z","timestamp":1282347567000},"page":"51-75","source":"Crossref","is-referenced-by-count":11,"title":["Lossy Counter Machines Decidability Cheat Sheet"],"prefix":"10.1007","author":[{"given":"Philippe","family":"Schnoebelen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1\u20132","key":"4_CR1","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.ic.2004.12.001","volume":"197","author":"P.A. Abdulla","year":"2005","unstructured":"Abdulla, P.A., Baier, C., Purushothaman Iyer, S., Jonsson, B.: Simulating perfect channels with probabilistic lossy channels. Information and Computation\u00a0197(1\u20132), 22\u201340 (2005)","journal-title":"Information and Computation"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-540-78499-9_4","volume-title":"Foundations of Software Science and Computational Structures","author":"P.A. Abdulla","year":"2008","unstructured":"Abdulla, P.A., Ben Henda, N., de Alfaro, L., Mayr, R., Sandberg, S.: Stochastic games with lossy channels. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol.\u00a04962, pp. 35\u201349. Springer, Heidelberg (2008)"},{"issue":"2","key":"4_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.ic.2005.05.008","volume":"202","author":"P.A. Abdulla","year":"2005","unstructured":"Abdulla, P.A., Bertrand, N., Rabinovich, A., Schnoebelen, P.: Verification of probabilistic systems with faulty communication. Information and Computation\u00a0202(2), 141\u2013165 (2005)","journal-title":"Information and Computation"},{"issue":"1","key":"4_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1093\/logcom\/exm062","volume":"18","author":"P.A. Abdulla","year":"2008","unstructured":"Abdulla, P.A., Bouajjani, A., d\u2019Orso, J.: Monotonic and downward closed games. Journal of Logic and Computation\u00a018(1), 153\u2013169 (2008)","journal-title":"Journal of Logic and Computation"},{"issue":"1\/2","key":"4_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1006\/inco.1999.2843","volume":"160","author":"P.A. Abdulla","year":"2000","unstructured":"Abdulla, P.A., \u010cer\u0101ns, K., Jonsson, B., Tsay, Y.-K.: Algorithmic analysis of programs with well quasi-ordered domains. Information and Computation\u00a0160(1\/2), 109\u2013127 (2000)","journal-title":"Information and Computation"},{"issue":"1","key":"4_CR6","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1006\/inco.1996.0083","volume":"130","author":"P.A. Abdulla","year":"1996","unstructured":"Abdulla, P.A., Jonsson, B.: Undecidable verification problems for programs with unreliable channels. Information and Computation\u00a0130(1), 71\u201390 (1996)","journal-title":"Information and Computation"},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1006\/inco.1996.0053","volume":"127","author":"P.A. Abdulla","year":"1996","unstructured":"Abdulla, P.A., Jonsson, B.: Verifying programs with unreliable channels. Information and Computation\u00a0127(2), 91\u2013101 (1996)","journal-title":"Information and Computation"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/3-540-60218-6_25","volume-title":"CONCUR \u201995 Concurrency Theory","author":"P.A. Abdulla","year":"1995","unstructured":"Abdulla, P.A., Kindahl, M.: Decidability of simulation and bisimulation between lossy channel systems and finite state systems. In: Lee, I., Smolka, S.A. (eds.) CONCUR 1995. LNCS, vol.\u00a0962, pp. 333\u2013347. Springer, Heidelberg (1995)"},{"key":"4_CR9","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/11916277_24","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"C. Baier","year":"2006","unstructured":"Baier, C., Bertrand, N., Schnoebelen, P.: On computing fixpoints in well-structured regular model checking, with applications to lossy channel systems. In: Hermann, M., Voronkov, A. (eds.) LPAR 2006. LNCS (LNAI), vol.\u00a04246, pp. 347\u2013361. Springer, Heidelberg (2006)"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Baier, C., Bertrand, N., Schnoebelen, P.: Verifying nondeterministic probabilistic channel systems against \u03c9-regular linear-time properties. ACM Trans. Computational Logic\u00a09(1) (2007)","DOI":"10.1145\/1297658.1297663"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/3-540-49116-3_30","volume-title":"STACS 99","author":"A. Bouajjani","year":"1999","unstructured":"Bouajjani, A., Mayr, R.: Model checking lossy vector addition systems. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 323\u2013333. Springer, Heidelberg (1999)"},{"issue":"1\u20132","key":"4_CR12","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0304-3975(88)90098-9","volume":"59","author":"M.C. Browne","year":"1988","unstructured":"Browne, M.C., Clarke, E.M., Grumberg, O.: Characterizing finite Kripke structures in propositional temporal logic. Theoretical Computer Science\u00a059(1\u20132), 115\u2013131 (1988)","journal-title":"Theoretical Computer Science"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/B978-044482830-9\/50027-8","volume-title":"Handbook of Process Algebra, ch. 9","author":"O. Bukart","year":"2001","unstructured":"Bukart, O., Caucal, D., Moller, F., Steffen, B.: Verification on infinite structures. In: Bergstra, J.A., Ponse, A., Smolka, S.A. (eds.) Handbook of Process Algebra, ch. 9, pp. 545\u2013623. Elsevier, Amsterdam (2001)"},{"key":"4_CR14","first-page":"50","volume-title":"Proc. STOC \u201976","author":"E. Cardoza","year":"1976","unstructured":"Cardoza, E., Lipton, R., Meyer, A.R.: Exponential space complete problems for Petri nets and commutative subgroups. In: Proc. STOC \u201976, pp. 50\u201354. ACM Press, New York (1976)"},{"issue":"1","key":"4_CR15","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/inco.1996.0003","volume":"124","author":"G. C\u00e9c\u00e9","year":"1996","unstructured":"C\u00e9c\u00e9, G., Finkel, A., Purushothaman Iyer, S.: Unreliable channels are easier to verify than perfect channels. Information and Computation\u00a0124(1), 20\u201331 (1996)","journal-title":"Information and Computation"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","volume-title":"Proc. DLT 2010","author":"P. Chambart","year":"2010","unstructured":"Chambart, P., Schnoebelen, P.: Computing blocker sets for the Regular Post Embedding Problem. In: Proc. DLT 2010. LNCS. Springer, Heidelberg (to appear, 2010)"},{"issue":"1","key":"4_CR17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(86)90169-6","volume":"43","author":"P. Clote","year":"1986","unstructured":"Clote, P.: On the finite containment problem for Petri nets. Theoretical Computer Science\u00a043(1), 99\u2013105 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"3-4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"311","DOI":"10.3166\/jancl.16.311-347","volume":"16","author":"S. Demri","year":"2006","unstructured":"Demri, S.: Linear-time temporal logics with Presburger constraints: An\u00a0overview. J. Applied Non-Classical Logics\u00a016(3-4), 311\u2013347 (2006)","journal-title":"J. Applied Non-Classical Logics"},{"key":"4_CR19","first-page":"17","volume-title":"Proc. LICS 2006","author":"S. Demri","year":"2006","unstructured":"Demri, S., Lazi\u0107, R.: LTL with the freeze quantifier and register automata. In: Proc. LICS 2006, pp. 17\u201326. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BFb0055044","volume-title":"Automata, Languages and Programming","author":"C. Dufourd","year":"1998","unstructured":"Dufourd, C., Finkel, A., Schnoebelen, P.: Reset nets between decidability and undecidability. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 103\u2013115. Springer, Heidelberg (1998)"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/3-540-48523-6_27","volume-title":"Automata, Languages and Programming","author":"C. Dufourd","year":"1999","unstructured":"Dufourd, C., Jan\u010dar, P., Schnoebelen, P.: Boundedness of reset P\/T nets. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 301\u2013310. Springer, Heidelberg (1999)"},{"key":"4_CR22","first-page":"995","volume-title":"Handbook of Theoretical Computer Science, ch. 16","author":"E.A. Emerson","year":"1990","unstructured":"Emerson, E.A.: Temporal and modal logic. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, ch. 16, vol.\u00a0B, pp. 995\u20131072. Elsevier, Amsterdam (1990)"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Figueira, D., Figueira, S., Schmitz, S., Schnoebelen, P.: Ackermann and primitive-recursive upper bounds with Dickson\u2019s lemma (2010) (in preparation)","DOI":"10.1109\/LICS.2011.39"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-03816-7_29","volume-title":"Mathematical Foundations of Computer Science 2009","author":"D. Figueira","year":"2009","unstructured":"Figueira, D., Segoufin, L.: Future-looking logics on data words and trees. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 331\u2013343. Springer, Heidelberg (2009)"},{"key":"4_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/3-540-18088-5_43","volume-title":"Automata, Languages and Programming","author":"A. Finkel","year":"1987","unstructured":"Finkel, A.: A generalization of the procedure of Karp and Miller to well structured transition systems. In: Ottmann, T. (ed.) ICALP 1987. LNCS, vol.\u00a0267, pp. 499\u2013508. Springer, Heidelberg (1987)"},{"issue":"2","key":"4_CR26","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/0890-5401(90)90009-7","volume":"89","author":"A. Finkel","year":"1990","unstructured":"Finkel, A.: Reduction and covering of infinite reachability trees. Information and Computation\u00a089(2), 144\u2013179 (1990)","journal-title":"Information and Computation"},{"key":"4_CR27","unstructured":"Finkel, A., Goubault-Larrecq, J.: Forward analysis for\u00a0WSTS, part\u00a0I: Completions. In: Proc. STACS 2009. Leibniz International Proceedings in Informatics, vol.\u00a03, pp. 433\u2013444. Leibniz-Zentrum f\u00fcr Informatik (2009)"},{"issue":"1\u20132","key":"4_CR28","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(00)00102-X","volume":"256","author":"A. Finkel","year":"2001","unstructured":"Finkel, A., Schnoebelen, P.: Well-structured transition systems everywhere! Theoretical Computer Science\u00a0256(1\u20132), 63\u201392 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"4_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1042038.1042039","volume":"6","author":"T.A. Henzinger","year":"2005","unstructured":"Henzinger, T.A., Majumdar, R., Raskin, J.-F.: A classification of symbolic transition systems. ACM Trans. Computational Logic\u00a06(1), 1\u201332 (2005)","journal-title":"ACM Trans. Computational Logic"},{"issue":"2","key":"4_CR30","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0304-3975(95)00037-W","volume":"148","author":"P. Jan\u010dar","year":"1995","unstructured":"Jan\u010dar, P.: Undecidability of bisimilarity for Petri nets and some related problems. Theoretical Computer Science\u00a0148(2), 281\u2013301 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"4_CR31","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/S0304-3975(00)00027-X","volume":"258","author":"P. Jan\u010dar","year":"2001","unstructured":"Jan\u010dar, P., Ku\u010dera, A., Mayr, R.: Deciding bisimulation-like equivalences with finite-state processes. Theoretical Computer Science\u00a0258(1\u20132), 409\u2013433 (2001)","journal-title":"Theoretical Computer Science"},{"key":"4_CR32","first-page":"131","volume-title":"Proc. LICS 2007","author":"M. Jurdzi\u0144ski","year":"2007","unstructured":"Jurdzi\u0144ski, M., Lazi\u0107, R.: Alternation-free modal mu-calculus for data trees. In: Proc. LICS 2007, pp. 131\u2013140. IEEE Comp. Soc. Press, Los Alamitos (2007)"},{"key":"4_CR33","unstructured":"Kracht, M.: A new proof of a theorem by Ginsburg and Spanier. Dept. Linguistics, UCLA (December 2002) (manuscript)"},{"issue":"3","key":"4_CR34","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0097-3165(72)90063-5","volume":"13","author":"J.B. Kruskal","year":"1972","unstructured":"Kruskal, J.B.: The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combinatorial Theory, Series A\u00a013(3), 297\u2013305 (1972)","journal-title":"Journal of Combinatorial Theory, Series A"},{"issue":"2\u20133","key":"4_CR35","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.tcs.2006.01.021","volume":"358","author":"A. Ku\u010dera","year":"2006","unstructured":"Ku\u010dera, A., Schnoebelen, P.: A general approach to comparing infinite-state systems with their finite-state specifications. Theoretical Computer Science\u00a0358(2\u20133), 315\u2013333 (2006)","journal-title":"Theoretical Computer Science"},{"key":"4_CR36","first-page":"303","volume-title":"Proc. STOC \u201974","author":"J. Leeuwen van","year":"1974","unstructured":"van Leeuwen, J.: A partial solution to the reachability-problem for vector-addition systems. In: Proc. STOC \u201974, pp. 303\u2013309. ACM Press, New York (1974)"},{"key":"4_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/978-3-642-00768-2_18","volume-title":"Proc. TACAS 2009","author":"J. Leroux","year":"2009","unstructured":"Leroux, J., Point, G.: TaPAS: The Talence Presburger Arithmetic Suite. In: Kowalewski, S., Philippou, A. (eds.) Proc. TACAS 2009. LNCS, vol.\u00a05505, pp. 182\u2013185. Springer, Heidelberg (2009)"},{"key":"4_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/10719839_37","volume-title":"LATIN 2000: Theoretical Informatics","author":"R. Mayr","year":"2000","unstructured":"Mayr, R.: Undecidable problems in unreliable computations. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 377\u2013386. Springer, Heidelberg (2000)"},{"issue":"1\u20133","key":"4_CR39","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(02)00646-1","volume":"297","author":"R. Mayr","year":"2003","unstructured":"Mayr, R.: Undecidable problems in unreliable computations. Theoretical Computer Science\u00a0297(1\u20133), 337\u2013354 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"4_CR40","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0304-3975(84)90029-X","volume":"32","author":"K. McAloon","year":"1984","unstructured":"McAloon, K.: Petri nets and large finite sets. Theoretical Computer Science\u00a032(1\u20132), 173\u2013183 (1984)","journal-title":"Theoretical Computer Science"},{"key":"4_CR41","series-title":"Electronic Notes in Theor. Comp. Sci","first-page":"69","volume-title":"Proc. AVoCS 2004","author":"J.-F. Raskin","year":"2005","unstructured":"Raskin, J.-F., Samuelides, M., Van Begin, L.: Games for counting abstractions. In: Proc. AVoCS 2004. Electronic Notes in Theor. Comp. Sci, vol.\u00a0128(6), pp. 69\u201385. Elsevier Science, Amsterdam (2005)"},{"key":"4_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/3-540-45500-0_19","volume-title":"Theoretical Aspects of Computer Software","author":"P. Schnoebelen","year":"2001","unstructured":"Schnoebelen, P.: Bisimulation and other undecidable equivalences for lossy channel systems. In: Kobayashi, N., Pierce, B.C. (eds.) TACS 2001. LNCS, vol.\u00a02215, pp. 385\u2013399. Springer, Heidelberg (2001)"},{"issue":"5","key":"4_CR43","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(01)00337-4","volume":"83","author":"P. Schnoebelen","year":"2002","unstructured":"Schnoebelen, P.: Verifying lossy channel systems has nonprimitive recursive complexity. Information Processing Letters\u00a083(5), 251\u2013261 (2002)","journal-title":"Information Processing Letters"},{"key":"4_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1007\/978-3-642-15155-2_54","volume-title":"MFCS 2010","author":"P. Schnoebelen","year":"2010","unstructured":"Schnoebelen, P.: Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets. In: Hlin\u011bny, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 616\u2013628. Springer, Heidelberg (2010)"},{"key":"4_CR45","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0304-3975(82)90067-6","volume":"18","author":"J. Sifakis","year":"1982","unstructured":"Sifakis, J.: A unified approach for studying the properties of transitions systems. Theoretical Computer Science\u00a018, 227\u2013258 (1982)","journal-title":"Theoretical Computer Science"},{"key":"4_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1007\/978-3-642-03816-7_60","volume-title":"Mathematical Foundations of Computer Science 2009","author":"T. Tan","year":"2009","unstructured":"Tan, T.: On pebble automata for data languages with decidable emptiness problem. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 712\u2013723. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15349-5_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:04:56Z","timestamp":1606169096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15349-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153488","9783642153495"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15349-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}