{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T01:13:41Z","timestamp":1648862021524},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,1,13]],"date-time":"2009-01-13T00:00:00Z","timestamp":1231804800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2009,5]]},"DOI":"10.1007\/s00236-008-0088-x","type":"journal-article","created":{"date-parts":[[2009,1,12]],"date-time":"2009-01-12T01:07:05Z","timestamp":1231722425000},"page":"169-191","source":"Crossref","is-referenced-by-count":4,"title":["Hardness of equivalence checking for composed finite-state systems"],"prefix":"10.1007","volume":"46","author":[{"given":"Zden\u011bk","family":"Sawa","sequence":"first","affiliation":[]},{"given":"Petr","family":"Jan\u010dar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,13]]},"reference":[{"issue":"6A","key":"88_CR1","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/BF03180566","volume":"4","author":"J. Balc\u00e1zar","year":"1992","unstructured":"Balc\u00e1zar J., Gabarr\u00f3 J., S\u00e1ntha M.: Deciding bisimilarity is P-complete. Formal Aspects Comput. 4(6A), 638\u2013648 (1992)","journal-title":"Formal Aspects Comput."},{"issue":"1","key":"88_CR2","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra A.K., Kozen D.C., Stockmeyer L.J.: Alternation. J. ACM. 28(1), 114\u2013133 (1981)","journal-title":"J. ACM."},{"key":"88_CR3","first-page":"3","volume-title":"Handbook of Process Algebra, chap. The Linear Time\u2014Branching Time Spectrum","author":"R. Glabbeek van","year":"2001","unstructured":"van Glabbeek R.: Handbook of process algebra. In: Bergstra, J., Ponse, A., Smolka, S. (eds.) Handbook of Process Algebra, chap. The Linear Time\u2014Branching Time Spectrum, pp. 3\u201399. Elsevier, Amsterdam (2001)"},{"key":"88_CR4","doi-asserted-by":"crossref","unstructured":"Groote, J.F., Moller, F.: Verification of parallel systems via decomposition. In: Proceedings of Third International Conference on Concurrency Theory. Lecture Notes in Computer Science, vol. 630, pp. 62\u201376. Springer, Heidelberg (1992)","DOI":"10.1007\/BFb0084783"},{"key":"88_CR5","volume-title":"Communcating Sequential Processes","author":"C.A.R. Hoare","year":"1985","unstructured":"Hoare C.A.R.: Communcating Sequential Processes. Prentice-Hall, Englewood Cliffs (1985)"},{"key":"88_CR6","first-page":"53","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1998","unstructured":"Immerman, N.: Descriptive Complexity, pp. 53\u201354. Springer, Heidelberg (1998)"},{"key":"88_CR7","doi-asserted-by":"crossref","unstructured":"Jan\u010dar, P., Srba, J.: Undecidability of bisimilarity by Defender\u2019s forcing. J. ACM. 55(1) (2008)","DOI":"10.1145\/1326554.1326559"},{"issue":"1","key":"88_CR8","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0890-5401(90)90025-D","volume":"86","author":"P.C. Kanellakis","year":"1990","unstructured":"Kanellakis P.C., Smolka S.A.: CCS expressions, finite state processes, and three problems of equivalence. Inf. Comput. 86(1), 43\u201368 (1990)","journal-title":"Inf. Comput."},{"key":"88_CR9","doi-asserted-by":"crossref","unstructured":"Laroussinie, F., Schnoebelen, P.: The state explosion problem from trace to bisimulation equivalence. In: Proceedings of the 3rd International Conference Foundations of Software Science and Computation Structures (FOSSACS\u20192000), Berlin, Germany, March\u2013April 2000. Lecture Notes in Computer Science, vol. 1784, pp. 192\u2013207. Springer, Heidelberg (2000)","DOI":"10.1007\/3-540-46432-8_13"},{"key":"88_CR10","first-page":"119","volume":"5","author":"A. Mansfield","year":"1983","unstructured":"Mansfield, A.: On the computational complexity of a merge recognition problem. DAMATH: Discrete Appl. Math. Combin. Oper. Res. Comput. Sci. 5, 119\u2013122 (1983)","journal-title":"DAMATH: Discrete Appl. Math. Combin. Oper. Res. Comput. Sci."},{"key":"88_CR11","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: 13th Annual Symposium on Switching and Automata Theory, pp. 125\u2013129. IEEE, New York (1972)","DOI":"10.1109\/SWAT.1972.29"},{"key":"88_CR12","volume-title":"Communication and Concurrency","author":"R. Milner","year":"1989","unstructured":"Milner R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989)"},{"issue":"6","key":"88_CR13","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige R., Tarjan R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973\u2013989 (1987)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"88_CR14","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1006\/inco.1997.2661","volume":"139","author":"A. Rabinovich","year":"1997","unstructured":"Rabinovich A.: Complexity of equivalence problems for concurrent systems of finite agents. Inf. Comput. 139(2), 111\u2013129 (1997)","journal-title":"Inf. Comput."},{"key":"88_CR15","doi-asserted-by":"crossref","unstructured":"Sawa, Z.: Equivalence checking of non-flat systems is EXPTIME-hard. In: Proceedings of CONCUR 2003. Lecture Notes in Computer Science, vol. 2761, pp. 237\u2013250. Springer, Heidelberg (2003)","DOI":"10.1007\/978-3-540-45187-7_16"},{"issue":"5","key":"88_CR16","first-page":"513","volume":"24","author":"Z. Sawa","year":"2005","unstructured":"Sawa Z., Jan\u010dar P.: Behavioural equivalences on finite-state systems are PTIME-hard. Comput. Inform. 24(5), 513\u2013528 (2005)","journal-title":"Comput. Inform."},{"key":"88_CR17","doi-asserted-by":"crossref","unstructured":"Shukla, S.K., Hunt, H.B., Rosenkrantz, D.J., Stearns, R.E.: On the complexity of relational problems for finite state processes. In: Proceedings of ICALP\u201996. Lecture Notes in Computer Science, vol. 1099, pp. 466\u2013477. Springer, Heidelberg (1996)","DOI":"10.1007\/3-540-61440-0_151"},{"key":"88_CR18","doi-asserted-by":"crossref","unstructured":"Valmari, A., Kervinen, A.: Alphabet-based synchronisation is exponentially cheaper. In: Proceedings of CONCUR 2002. Lecture Notes in Computer Science, vol. 2421, pp. 161\u2013176 (2002)","DOI":"10.1007\/3-540-45694-5_12"},{"issue":"3","key":"88_CR19","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0022-0000(84)90018-7","volume":"28","author":"M.K. Warmuth","year":"1984","unstructured":"Warmuth M.K., Haussler D.: On the complexity of iterated shuffle. J. Comp. Syst. Sci. 28(3), 345\u2013358 (1984)","journal-title":"J. Comp. Syst. Sci."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-008-0088-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-008-0088-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-008-0088-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T09:41:55Z","timestamp":1558690915000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-008-0088-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,13]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["88"],"URL":"https:\/\/doi.org\/10.1007\/s00236-008-0088-x","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,13]]}}}