{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:26Z","timestamp":1740109406238,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"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":[[2011,1]]},"DOI":"10.1007\/s00224-009-9227-1","type":"journal-article","created":{"date-parts":[[2009,7,31]],"date-time":"2009-07-31T10:49:38Z","timestamp":1249037378000},"page":"93-131","source":"Crossref","is-referenced-by-count":3,"title":["Fixpoint Logics over Hierarchical Structures"],"prefix":"10.1007","volume":"48","author":[{"given":"Stefan","family":"G\u00f6ller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,8,1]]},"reference":[{"issue":"3","key":"9227_CR1","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 Trans. Program. Lang. Syst. (TOPLAS) 23(3), 273\u2013303 (2001)","journal-title":"ACM Trans. Program. Lang. Syst. (TOPLAS)"},{"key":"9227_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/3-540-56992-8_8","volume-title":"Proceedings of the 6th Workshop on Computer Science Logic (CSL\u201992)","author":"U. Bosse","year":"1993","unstructured":"Bosse, U.: An \u201cEhrenfeucht-Fra\u00efss\u00e9 Game\u201d for fixpoint logic and stratified fixpoint logic. In: Proceedings of the 6th Workshop on Computer Science Logic (CSL\u201992). Lecture Notes in Computer Science, vol. 707, pp. 100\u2013114. Springer, Berlin (1993)"},{"key":"9227_CR3","unstructured":"Bosse, U.: Zur Modelltheorie der Fixpunktlogik. Ph.D. thesis, Universit\u00e4t Freiburg, 1994"},{"issue":"1","key":"9227_CR4","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. Assoc. Comput. Mach. 28(1), 114\u2013133 (1981)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9227_CR5","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"key":"9227_CR6","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"9227_CR7","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1991","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Springer, Berlin (1991)"},{"key":"9227_CR8","first-page":"132","volume-title":"Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS\u201991)","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy (extended abstract). In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS\u201991), pp. 132\u2013142. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"9227_CR9","first-page":"267","volume-title":"Proceedings of the First Annual IEEE Symposium on Logic in Computer Science (LICS\u201986)","author":"E.A. Emerson","year":"1986","unstructured":"Emerson, E.A., Lei, C.-L.: Efficient model checking in fragments of the propositional mu-calculus (extended abstract). In: Proceedings of the First Annual IEEE Symposium on Logic in Computer Science (LICS\u201986), pp. 267\u2013278. IEEE Computer Society Press, Los Alamitos (1986)"},{"issue":"1\u20132","key":"9227_CR10","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1016\/S0304-3975(00)00034-7","volume":"258","author":"E.A. Emerson","year":"2001","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model checking for the \u03bc-calculus and its fragments. Theor. Comput. Sci. 258(1\u20132), 491\u2013522 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"9227_CR11","series-title":"Handbook of Formal Languages","first-page":"125","volume-title":"Beyond Words","author":"J. Engelfriet","year":"1997","unstructured":"Engelfriet, J.: Context-free graph grammars. In: Rozenberg, G., Salomaa, A. (eds.) Beyond Words. Handbook of Formal Languages, vol.\u00a03, pp. 125\u2013213. Springer, Berlin (1997)"},{"key":"9227_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36387-4","volume-title":"Automata, Logics, and Infinite Games","author":"E. Gr\u00e4del","year":"2002","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T.: Automata, Logics, and Infinite Games. Lecture Notes in Computer Science, vol.\u00a02500, Springer, Berlin (2002)"},{"key":"9227_CR13","series-title":"Lecture Notes in Computer Science","volume-title":"Hyperedge Replacement: Grammars and Languages","author":"A. Habel","year":"1992","unstructured":"Habel, A.: Hyperedge Replacement: Grammars and Languages. Lecture Notes in Computer Science, vol.\u00a0643, Springer, Berlin (1992)"},{"issue":"1\u20133","key":"9227_CR14","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"Immerman, N.: Relational queries computable in polynomial time. Inf. Control 68(1\u20133), 86\u2013104 (1986)","journal-title":"Inf. Control"},{"issue":"3","key":"9227_CR15","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzi\u0144ski","year":"1998","unstructured":"Jurdzi\u0144ski, M.: Deciding the winner in parity games is in UP and co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998)","journal-title":"Inf. Process. Lett."},{"key":"9227_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/3-540-46541-3_24","volume-title":"Proceedings of the17th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2000)","author":"M. Jurdzi\u0144ski","year":"2000","unstructured":"Jurdzi\u0144ski, M.: Small progress measures for solving parity games. In: Proceedings of the17th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2000). Lecture Notes in Computer Science, vol. 1770, pp. 290\u2013301. Springer, Berlin (2000)"},{"key":"9227_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/10722167_7","volume-title":"Proceedings of the 12th International Conference on Computer Aided Verification (CAV 2000)","author":"O. Kupferman","year":"2000","unstructured":"Kupferman, O., Vardi, M.Y.: An automata-theoretic approach to reasoning about infinite-state systems. In: Proceedings of the 12th International Conference on Computer Aided Verification (CAV 2000). Lecture Notes in Computer Science, vol. 1855, pp. 36\u201352. Springer, Berlin (2000)"},{"issue":"4","key":"9227_CR18","first-page":"281","volume":"33","author":"R.E. Ladner","year":"1977","unstructured":"Ladner, R.E.: Application of model theoretic games to discrete linear orders and finite automata. Inf. Comput. 33(4), 281\u2013303 (1977)","journal-title":"Inf. Comput."},{"issue":"3","key":"9227_CR19","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1145\/65950.65952","volume":"36","author":"T. Lengauer","year":"1989","unstructured":"Lengauer, T.: Hierarchical planarity testing algorithms. J. Assoc. Comput. Mach. 36(3), 474\u2013509 (1989)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9227_CR20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0022-0000(92)90004-3","volume":"44","author":"T. Lengauer","year":"1992","unstructured":"Lengauer, T., Wagner, K.W.: The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems. J. Comput. Syst. Sci. 44, 63\u201393 (1992)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"9227_CR21","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1137\/0217068","volume":"17","author":"T. Lengauer","year":"1988","unstructured":"Lengauer, T., Wanke, E.: Efficient solution of connectivity problems on hierarchically defined graphs. SIAM J. Comput. 17(6), 1063\u20131080 (1988)","journal-title":"SIAM J. Comput."},{"key":"9227_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer, Berlin (2004)"},{"key":"9227_CR23","doi-asserted-by":"crossref","unstructured":"Lohrey, M.: Model-checking hierarchical structures. J. Comput. Syst. Sci. (2007, to appear). LICS, pp.\u00a0168\u2013177 (2005). http:\/\/dx.doi.org\/10.1109\/LICS.2005.29","DOI":"10.1109\/LICS.2005.29"},{"issue":"2","key":"9227_CR24","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.tcs.2006.07.024","volume":"363","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M., Maneth, S.: The complexity of tree automata and XPath on grammar-compressed trees. Theor. Comput. Sci. 363(2), 196\u2013210 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"9227_CR25","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"J.A. Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic aspects of the Feferman-Vaught theorem. Ann. Pure Appl. Logic 126(1\u20133), 159\u2013213 (2004)","journal-title":"Ann. Pure Appl. Logic"},{"key":"9227_CR26","doi-asserted-by":"crossref","unstructured":"Makowsky, J.A., Ravve, E.V.: Incremental model checking for fixed point properties on decomposable structures. http:\/\/www.cs.technion.ac.il\/~admlogic\/TR\/readme.html (1995)","DOI":"10.1007\/3-540-60246-1_159"},{"issue":"3","key":"9227_CR27","first-page":"275","volume":"1","author":"M.V. Marathe","year":"1994","unstructured":"Marathe, M.V., Hunt III, H.B., Ravi, S.S.: The complexity of approximation PSPACE-complete problems for hierarchical specifications. Nord. J. Comput. 1(3), 275\u2013316 (1994)","journal-title":"Nord. J. Comput."},{"issue":"1\u20132","key":"9227_CR28","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0304-3975(96)00008-4","volume":"174","author":"M.V. Marathe","year":"1997","unstructured":"Marathe, M.V., Radhakrishnan, V., Hunt III, H.B., Ravi, S.S.: Hierarchically specified unit disk graphs. Theor. Comput. Sci. 174(1\u20132), 23\u201365 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9227_CR29","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.1137\/S0097539795285254","volume":"27","author":"M.V. Marathe","year":"1998","unstructured":"Marathe, M.V., Hunt III, H.B., Stearns, R.E., Radhakrishnan, V.: Approximation algorithms for PSPACE-hard hierarchically and periodically specified problems. SIAM J. Comput. 27(5), 1237\u20131261 (1998)","journal-title":"SIAM J. Comput."},{"key":"9227_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/978-3-540-45069-6_7","volume-title":"Proceedings of the 15th International Conference on Computer Aided Verification (CAV 2003)","author":"J. Obdr\u017e\u00e1lek","year":"2003","unstructured":"Obdr\u017e\u00e1lek, J.: Fast mu-calculus model checking when tree-width is bounded. In: Proceedings of the 15th International Conference on Computer Aided Verification (CAV 2003). Lecture Notes in Computer Science, vol. 2725, pp. 80\u201392. Springer, Berlin (2003)"},{"key":"9227_CR31","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison Wesley, Reading (1994)"},{"key":"9227_CR32","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-642-60207-8_23","volume-title":"Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 262\u2013272. Springer, Berlin (1999)"},{"issue":"1","key":"9227_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci. 3(1), 1\u201322 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"9227_CR34","first-page":"137","volume-title":"Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing (STOC 1982)","author":"M.Y. Vardi","year":"1982","unstructured":"Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing (STOC 1982), pp. 137\u2013146. ACM, New York (1982)"},{"key":"9227_CR35","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1145\/212433.212474","volume-title":"Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 1995)","author":"M.Y. Vardi","year":"1995","unstructured":"Vardi, M.Y.: On the complexity of bounded-variable queries. In: Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 1995), pp. 266\u2013276. ACM, New York (1995)"},{"key":"9227_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/3-540-44450-5_10","volume-title":"Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2000)","author":"I. Walukiewicz","year":"2000","unstructured":"Walukiewicz, I.: Model checking CTL properties of pushdown systems. In: Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2000). Lecture Notes in Computer Science, vol. 1974, pp. 127\u2013138. Springer, Berlin (2000)"},{"issue":"2","key":"9227_CR37","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"I. Walukiewicz","year":"2001","unstructured":"Walukiewicz, I.: Pushdown processes: games and model-checking. Inf. Comput. 164(2), 234\u2013263 (2001)","journal-title":"Inf. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9227-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9227-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9227-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:38Z","timestamp":1558684298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9227-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["9227"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9227-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2009,8,1]]}}}