{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:36:17Z","timestamp":1725888977499},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319602516"},{"type":"electronic","value":"9783319602523"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-60252-3_9","type":"book-chapter","created":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T10:59:13Z","timestamp":1496401153000},"page":"114-127","source":"Crossref","is-referenced-by-count":0,"title":["A Parametrized Analysis of Algorithms on Hierarchical Graphs"],"prefix":"10.1007","author":[{"given":"Rachel","family":"Faran","sequence":"first","affiliation":[]},{"given":"Orna","family":"Kupferman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/3-540-48523-6_14","volume-title":"Automata, Languages and Programming","author":"R Alur","year":"1999","unstructured":"Alur, R., Kannan, S., Yannakakis, M.: Communicating hierarchical state machines. In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 169\u2013178. Springer, Heidelberg (1999). doi:\n10.1007\/3-540-48523-6_14"},{"issue":"3","key":"9_CR2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/503502.503503","volume":"23","author":"R Alur","year":"2001","unstructured":"Alur, R., Yannakakis, M.: Model checking of hierarchical state machines. ACM TOPLAS 23(3), 273\u2013303 (2001)","journal-title":"ACM TOPLAS"},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ic.2011.10.008","volume":"210","author":"B Aminof","year":"2012","unstructured":"Aminof, B., Kupferman, O., Murano, A.: Improved model checking of hierarchical systems. Inf. Comput. 210, 68\u201386 (2012)","journal-title":"Inf. Comput."},{"issue":"3","key":"9_CR4","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"C Barrett","year":"2000","unstructured":"Barrett, C., Jacob, R., Marathe, M.: Formal-language-constrained path problems. SIAM J. Comput. 30(3), 809\u2013837 (2000)","journal-title":"SIAM J. Comput."},{"key":"9_CR5","volume-title":"Model Checking","author":"EM Clarke","year":"1999","unstructured":"Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (1999)"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-49213-5_1","volume-title":"Compositionality: The Significant Difference","author":"W-P Roever de","year":"1998","unstructured":"de Roever, W.-P.: The need for compositional proof systems: a survey. In: de Roever, W.-P., Langmaack, H., Pnueli, A. (eds.) COMPOS 1997. LNCS, vol. 1536, pp. 1\u201322. Springer, Heidelberg (1998). doi:\n10.1007\/3-540-49213-5_1"},{"key":"9_CR7","series-title":"Texts in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Heidelberg (2013)"},{"issue":"3","key":"9_CR8","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1145\/176584.176587","volume":"41","author":"D Drusinsky","year":"1994","unstructured":"Drusinsky, D., Harel, D.: On the power of bounded concurrency I: finite automata. J. ACM 41(3), 517\u2013539 (1994)","journal-title":"J. ACM"},{"issue":"3","key":"9_CR9","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8(3), 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"issue":"3","key":"9_CR10","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H Galperin","year":"1983","unstructured":"Galperin, H., Wigderson, A.: Succinct representations of graphs. Inf. Control 56(3), 183\u2013198 (1983)","journal-title":"Inf. Control"},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.2001.2920","volume":"173","author":"D Harel","year":"2002","unstructured":"Harel, D., Kupferman, O., Vardi, M.Y.: On the complexity of verifying concurrent transition systems. Inf. Comput. 173, 1\u201319 (2002)","journal-title":"Inf. Comput."},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Length of predicate calculus formulas as a new complexity measure. In: Proceedings of 20th FOCS, pp. 337\u2013347 (1979)","DOI":"10.1109\/SFCS.1979.21"},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-662-54577-5_13","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"O Kupferman","year":"2017","unstructured":"Kupferman, O., Tamir, T.: Hierarchical network formation games. In: Legay, A., Margaria, T. (eds.) TACAS 2017. LNCS, vol. 10205, pp. 229\u2013246. Springer, Heidelberg (2017). doi:\n10.1007\/978-3-662-54577-5_13"},{"issue":"2","key":"9_CR14","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1145\/333979.333987","volume":"47","author":"O Kupferman","year":"2000","unstructured":"Kupferman, O., Vardi, M.Y., Wolper, P.: An automata-theoretic approach to branching-time model checking. J. ACM 47(2), 312\u2013360 (2000)","journal-title":"J. ACM"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Lengauer, T.: The complexity of compacting hierarchically specified layouts of integrated circuits. In: Proceedings of 23rd FOCS, pp. 358\u2013368 (1982)","DOI":"10.1109\/SFCS.1982.92"},{"key":"9_CR16","first-page":"63","volume":"44","author":"T Lengauer","year":"1990","unstructured":"Lengauer, T., Wagner, K.W.: The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems. JCSS 44, 63\u201393 (1990)","journal-title":"JCSS"},{"issue":"6","key":"9_CR17","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1137\/0217068","volume":"17","author":"T Lengauer","year":"1988","unstructured":"Lengauer, T., Wanke, E.: Efficient solutions of connectivity problems on hierarchically defined graphs. SIAM J. Comput. 17(6), 1063\u20131081 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9_CR18","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01585506","volume":"7","author":"N Megiddo","year":"1974","unstructured":"Megiddo, N.: Optimal flows in networks with multiple sources and sinks. Math. Program. 7(1), 97\u2013107 (1974)","journal-title":"Math. Program."},{"issue":"6","key":"9_CR19","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"AO Mendelzon","year":"1995","unstructured":"Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput. 24(6), 1235\u20131258 (1995)","journal-title":"SIAM J. Comput."},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: Proceedings of 46th STOC, pp. 263\u2013272 (2014)","DOI":"10.1145\/2591796.2591834"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-60252-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T11:01:16Z","timestamp":1496401276000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-60252-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319602516","9783319602523"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60252-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}