{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T03:32:14Z","timestamp":1672975934656},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,10,6]],"date-time":"2007-10-06T00:00:00Z","timestamp":1191628800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,5]]},"DOI":"10.1007\/s00224-007-9054-1","type":"journal-article","created":{"date-parts":[[2007,10,5]],"date-time":"2007-10-05T15:22:24Z","timestamp":1191597744000},"page":"536-567","source":"Crossref","is-referenced-by-count":6,"title":["Pattern Matching and Membership for Hierarchical Message Sequence Charts"],"prefix":"10.1007","volume":"42","author":[{"given":"Blaise","family":"Genest","sequence":"first","affiliation":[]},{"given":"Anca","family":"Muscholl","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,6]]},"reference":[{"key":"9054_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1007\/3-540-48224-5_65","volume-title":"Proceedings of ICALP\u201901","author":"R. Alur","year":"2001","unstructured":"Alur, R., Etessami, K., Yannakakis, M.: Realizability and verification of MSC graphs. In: Proceedings of ICALP\u201901. Lecture Notes in Computer Science, vol.\u00a02076, pp.\u00a0797\u2013808. Springer, Berlin (2001) (Journal version in Theor. Comput. Sci. 331(1), 97\u2013114 (2005))"},{"issue":"2","key":"9054_CR2","first-page":"70","volume":"17","author":"R. Alur","year":"1996","unstructured":"Alur, R., Holzmann, G.H., Peled, D.A.: An analyzer for message sequence charts. Soft. Concepts Tools 17(2), 70\u201377 (1996)","journal-title":"Soft. Concepts Tools"},{"key":"9054_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/3-540-48523-6_14","volume-title":"Proceedings of ICALP\u201999","author":"R. Alur","year":"1999","unstructured":"Alur, R., Kannan, S., Yannakakis, M.: Communicating hierarchical state machines. In: Proceedings of ICALP\u201999. Lecture Notes in Computer Science, vol.\u00a01644, pp.\u00a0169\u2013178. Springer, Berlin (1999)"},{"key":"9054_CR4","doi-asserted-by":"crossref","unstructured":"Alur, R., Yannakakis, M.: Model checking of hierarchical state machines. In: Proceedings of SIGSOFT\u201998, pp. 175\u2013188 (1998) (Extended version in ACM Trans. Program. Lang. Syst. 23(3), 273\u2013303 (2001))","DOI":"10.1145\/503502.503503"},{"key":"9054_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/3-540-48320-9_10","volume-title":"Proceedings of CONCUR\u201999","author":"R. Alur","year":"1999","unstructured":"Alur, R., Yannakakis, M.: Model checking of message sequence charts. In: Proceedings of CONCUR\u201999. Lecture Notes in Computer Science, vol.\u00a01664, pp.\u00a0114\u2013129. Springer, Berlin (1999)"},{"key":"9054_CR6","unstructured":"Dalmau, V.: Computational complexity of problems over generalized formulas. Ph.D. thesis, Universitat polit\u00e9cnica de Catalunya (UPC) (2000)"},{"key":"9054_CR7","doi-asserted-by":"crossref","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16 (1965)","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"9054_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/3-540-45995-2_31","volume-title":"Proceedings of LATIN\u201902","author":"B. Genest","year":"2002","unstructured":"Genest, B., Muscholl, A.: Pattern matching and membership for hierarchical message sequence charts. In: Proceedings of LATIN\u201902. Lecture Notes in Computer Science, vol.\u00a02286, pp.\u00a0326\u2013340. Springer, Berlin (2002)"},{"key":"9054_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-540-24727-2_15","volume-title":"Proceedings of FoSSaCS\u201904","author":"B. Genest","year":"2004","unstructured":"Genest, B., Minea, M., Muscholl, A., Peled, D.: Specifying and verifying partial order properties using template MSCs. In: Proceedings of FoSSaCS\u201904. Lecture Notes in Computer Science, vol.\u00a02987, pp.\u00a0195\u2013209. Springer, Berlin (2004)"},{"key":"9054_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1007\/3-540-45465-9_56","volume-title":"Proceedings of ICALP\u201902","author":"B. Genest","year":"2002","unstructured":"Genest, B., Muscholl, A., Seidl, H., Zeitoun, M.: Infinite-state High-level MSCs: Model-checking and realizability. In: Proceedings of ICALP\u201902. Lecture Notes in Computer Science, vol. 2380, pp. 657\u2013668. Springer, Berlin (2002) (Journal version in J. Comput. Syst.\u00a0Sci. 72(4), 617\u2013647 (2006))"},{"issue":"3","key":"9054_CR11","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0167-6423(87)90035-9","volume":"8","author":"D. Harel","year":"1987","unstructured":"Harel, D.: Statecharts: a visual formulation for complex systems. Sci. Comput. Program. 8(3), 231\u2013274 (1987)","journal-title":"Sci. Comput. Program."},{"key":"9054_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/3-540-63141-0_18","volume-title":"Proceedings of CONCUR\u201997","author":"D. Harel","year":"1997","unstructured":"Harel, D., Kupferman, O., Vardi, M.Y.: On the complexity of verifying concurrent transition systems. In: Proceedings of CONCUR\u201997. Lecture Notes in Computer Science, vol. 1243, pp. 258\u2013272. Springer, Berlin (1997) (Journal version in Inform. Comput. 173(2), 143\u2013161 (2002))"},{"key":"9054_CR13","unstructured":"ITU-TS recommendation Z. 120 (1996)"},{"key":"9054_CR14","unstructured":"Lifshits, Y.: Solving classical string problems on compressed texts. Available at http:\/\/xxx.lanl.gov\/abs\/cs.DS\/0604058"},{"key":"9054_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/3-540-45694-5_13","volume-title":"Proceedings of CONCUR\u201902","author":"M. Lohrey","year":"2002","unstructured":"Lohrey, M.: Safe realizability of high-level message sequence charts. In: Proceedings of CONCUR\u201902. Lecture Notes in Computer Science, vol. 2421, pp. 177\u2013192. Springer, Berlin (2002) (Journal version in Theor. Comput. Sci. 309(1\u20133), 529\u2013554 (2003))"},{"key":"9054_CR16","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/0890-5401(90)90010-F","volume":"89","author":"H. Liu","year":"1990","unstructured":"Liu, H., Wrathall, C., Zeger, K.: Efficient solution of some problems in free partially commutative monoids. Inform. Comput. 89, 180\u2013198 (1990)","journal-title":"Inform. Comput."},{"key":"9054_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1007\/3-540-48224-5_66","volume-title":"Proceedings of ICALP\u201901","author":"P. Madhusudan","year":"2001","unstructured":"Madhusudan, P.: Reasoning about sequential and branching behaviours of message sequence graphs. In: Proceedings of ICALP\u201901. Lecture Notes in Computer Science, vol. 2076, pp. 809\u2013820. Springer, Berlin (2001)"},{"key":"9054_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-63220-4_45","volume-title":"Proceedings of CPM\u201997","author":"M. Miyazaki","year":"1997","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. In: Proceedings of CPM\u201997. Lecture Notes in Computer Science, vol. 1264, pp. 1\u201311. Springer, Berlin (1997)"},{"key":"9054_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/3-540-44618-4_37","volume-title":"Proceedings of CONCUR\u201900","author":"M. Mukund","year":"2000","unstructured":"Mukund, M., Narayan Kumar, K., Sohoni, M.: Synthesizing distributed finite-state systems from MSCs. In: Proceedings of CONCUR\u201900. Lecture Notes in Computer Science, vol. 1877, pp. 521\u2013535. Springer, Berlin (2000)"},{"key":"9054_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/3-540-48340-3_8","volume-title":"Proceedings of MFCS\u201999","author":"A. Muscholl","year":"1999","unstructured":"Muscholl, A., Peled, D.: Message sequence graphs and decision problems on Mazurkiewicz traces. In: Proceedings of MFCS\u201999. Lecture Notes in Computer Science, vol. 1672, pp. 81\u201391. Springer, Berlin (1999)"},{"key":"9054_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1007\/BFb0053553","volume-title":"Proceedings of FoSSaCS\u201998","author":"A. Muscholl","year":"1998","unstructured":"Muscholl, A., Peled, D., Su, Z.: Deciding properties of message sequence charts. In: Proceedings of FoSSaCS\u201998. Lecture Notes in Computer Science, vol. 1378, pp. 226\u2013242. Springer, Berlin (1998)"},{"key":"9054_CR22","first-page":"139","volume-title":"Proceedings of FORTE\/PSTV\u201900","author":"D. Peled","year":"2000","unstructured":"Peled, D.: Specification and verification of Message Sequence Charts. In: Proceedings of FORTE\/PSTV\u201900, pp. 139\u2013154. Kluwer, Dordrecht (2000)"},{"key":"9054_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Proceedings of ESA\u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: Proceedings of ESA\u201994. Lecture Notes in Computer Science, vol. 855, pp. 460\u2013470. Springer, Berlin (1994)"},{"key":"9054_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/3-540-47849-3_3","volume-title":"Proceedings of SOFSEM\u201999","author":"W. Rytter","year":"1999","unstructured":"Rytter, W.: Algorithms on compressed strings and arrays. In: Proceedings of SOFSEM\u201999. Lecture Notes in Computer Science, vol. 1725, pp. 48\u201365. Springer, Berlin (1999)"},{"key":"9054_CR25","first-page":"216","volume-title":"Proceedings of STOC\u201978","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of STOC\u201978, pp. 216\u2013226. Springer, Berlin (1978)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9054-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9054-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9054-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:34Z","timestamp":1558698694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9054-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,6]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["9054"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9054-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,6]]}}}