{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:09Z","timestamp":1760202609713,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240143"},{"type":"electronic","value":"9783540305507"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30550-7_29","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:06:05Z","timestamp":1278097565000},"page":"345-356","source":"Crossref","is-referenced-by-count":7,"title":["From Post Systems to the Reachability Problems for Matrix Semigroups and Multicounter Automata"],"prefix":"10.1007","author":[{"given":"Igor","family":"Potapov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","unstructured":"Bestel, J., Karhumaki, J.: Combinatorics on Words - A Tutorial, Bulletin of the EATCS, February 2003, pp. 178\u2013228 (2003)"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1016\/S0005-1098(00)00050-9","volume":"36","author":"V. Blondel","year":"2000","unstructured":"Blondel, V., Tsitsiklis, J.: A survey of computational complexity results in systems and control. Automatica\u00a036, 1249\u20131274 (2000)","journal-title":"Automatica"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Comon, H., Jurski, Y.: Multiple counters automata, safety analysis and Presburger arithmetic, Research Report LSV-98-1 (March 1998)","DOI":"10.1007\/BFb0028751"},{"key":"29_CR4","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, Ph.: 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":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/3-540-46541-3_29","volume-title":"STACS 2000","author":"A. Finkel","year":"2000","unstructured":"Finkel, A., Sutre, G.: Decidability of reachability problems for classes of two counters automata. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 346\u2013357. Springer, Heidelberg (2000)"},{"issue":"1","key":"29_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0890-5401(02)00027-5","volume":"181","author":"A. Finkel","year":"2003","unstructured":"Finkel, A., Purushothaman Iyer, S., Sutre, G.: Well-abstracted transition systems: application to FIFO automata. Inf. Comput.\u00a0181(1), 1\u201331 (2003)","journal-title":"Inf. Comput."},{"key":"29_CR7","unstructured":"Gaubert, S., Katz, R.: Reachability problems for products of matrices in semirings. arXiv:math.OC\/0310028, v1, 1-21 (2003)"},{"key":"29_CR8","volume-title":"Concrete Mathematics","author":"R. Graham","year":"1994","unstructured":"Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics, 2nd edn. Addison-Wesley, Reading (1994)","edition":"2"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/S0019-9958(84)80014-5","volume":"63","author":"M. Gouda","year":"1984","unstructured":"Gouda, M., Manning, E., Yu, Y.: On the progress of communication between two finite state machines. Information and control\u00a063, 200\u2013216 (1984)","journal-title":"Information and control"},{"issue":"4","key":"29_CR10","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1511\/2000.29.3334","volume":"88","author":"B. Hayes","year":"2000","unstructured":"Hayes, B.: On the Teeth of Wheels. American Scientist\u00a088(4), 296\u2013300 (2000)","journal-title":"American Scientist"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-44612-5_38","volume-title":"Mathematical Foundations of Computer Science 2000","author":"O.H. Ibarra","year":"2000","unstructured":"Ibarra, O.H., Su, J., Bultan, T., Dang, Z., Kemmerer, R.A.: Counter Machines: Decidable Properties and Applications to Verification Problems. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 426\u2013435. Springer, Heidelberg (2000)"},{"issue":"4","key":"29_CR12","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1145\/6490.6496","volume":"33","author":"R. Kannan","year":"1986","unstructured":"Kannan, R., Lipton, R.J.: Polynomial-time algorithm for the orbit problem. Journal of the ACM (JACM)\u00a033(4), 808\u2013821 (1986)","journal-title":"Journal of the ACM (JACM)"},{"key":"29_CR13","first-page":"49","volume":"3","author":"O. Kurganskyy","year":"1999","unstructured":"Kurganskyy, O., Potapov, I.: On the bound of algorithmic resolvability of correctness problems of automaton interaction through communication channels. Cybernetics and System Analysis\u00a03, 49\u201357 (1999)","journal-title":"Cybernetics and System Analysis"},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/978-3-540-28629-5_48","volume-title":"Mathematical Foundations of Computer Science 2004","author":"A. Lisitsa","year":"2004","unstructured":"Lisitsa, A., Potapov, I.: Membership and reachability problems for row-monomial transformations. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 623\u2013634. Springer, Heidelberg (2004)"},{"key":"29_CR15","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(99)00102-4","volume":"231","author":"M. Mergenstern","year":"2000","unstructured":"Mergenstern, M.: Frontier between decidability and undecidability: a survey. Theoretical Computer Science\u00a0231, 217\u2013251 (2000)","journal-title":"Theoretical Computer Science"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Matiyasevich, Y.V., Senizergues, G.: Decision problems for semi-Thue systems with a few rules. In: Proc. LICS 1996, pp. 523\u2013531 (1996)","DOI":"10.1109\/LICS.1996.561469"},{"key":"29_CR17","volume-title":"Computation: Finite and Infinite Machines","author":"M. Minsky","year":"1967","unstructured":"Minsky, M.: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"2354","DOI":"10.1103\/PhysRevLett.64.2354","volume":"64","author":"C. Moore","year":"1990","unstructured":"Moore, C.: Unpredictability and Undecidability in Dynamical Systems. Physical Review Letters\u00a064, 2354\u20132357 (1990)","journal-title":"Physical Review Letters"},{"key":"29_CR19","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01343730","volume":"152","author":"H. Wang","year":"1963","unstructured":"Wang, H.: Tag Systems and Lag Systems. Math. Ann.\u00a0152, 65\u201374 (1963)","journal-title":"Math. Ann."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30550-7_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T15:42:23Z","timestamp":1740238943000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30550-7_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240143","9783540305507"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30550-7_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}