{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:52:12Z","timestamp":1725565932568},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228493"},{"type":"electronic","value":"9783540278368"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_93","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T22:53:21Z","timestamp":1284591201000},"page":"1123-1135","source":"Crossref","is-referenced-by-count":3,"title":["On the Expressive Power of Monadic Least Fixed Point Logic"],"prefix":"10.1007","author":[{"given":"Nicole","family":"Schweikardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"93_CR1","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1006\/jcss.1999.1691","volume":"60","author":"M. Ajtai","year":"2000","unstructured":"Ajtai, M., Fagin, R., Stockmeyer, L.: The closure of Monadic NP. Journal of Computer and System Sciences\u00a060(3), 660\u2013716 (2000); Journal version of STOC 1998 paper","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"93_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0304-3975(97)00217-X","volume":"195","author":"J. Bradfield","year":"1998","unstructured":"Bradfield, J.: The modal \u03bc-calculus alternation hierarchy is strict. Theoretical Computer Science\u00a0195(2), 133\u2013153 (1998); Journal version of CONCUR 1996 paper","journal-title":"Theoretical Computer Science"},{"key":"93_CR3","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/inco.1998.2703","volume":"143","author":"A. Dawar","year":"1998","unstructured":"Dawar, A.: A restricted second order logic for finite structures. Information and Computation\u00a0143, 154\u2013174 (1998); Journal version of LCC 1994 paper","journal-title":"Information and Computation"},{"key":"93_CR4","unstructured":"Durand, A., Lautemann, C., More, M.: Counting results in weak formalisms. Technical Report 1998-14, Universit\u00e9 de Caen, France (1998)"},{"key":"93_CR5","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"issue":"6","key":"93_CR6","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J. Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. Journal of the ACM\u00a049(6), 716\u2013752 (2002); Journal version of ICDT 2001 paper","journal-title":"Journal of the ACM"},{"issue":"1","key":"93_CR7","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/962446.962450","volume":"51","author":"G. Gottlob","year":"2004","unstructured":"Gottlob, G., Koch, C.: Monadic datalog and the expressive power of web information extraction languages. Journal of the ACM\u00a051(1), 74\u2013113 (2004); Journal version of PODS 2002 paper","journal-title":"Journal of the ACM"},{"key":"93_CR8","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/BF01205055","volume":"4","author":"E. Grandjean","year":"1994","unstructured":"Grandjean, E.: Invariance properties of RAMs and linear time. Computational Complexity\u00a04, 62\u2013106 (1994)","journal-title":"Computational Complexity"},{"issue":"3","key":"93_CR9","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/S0097539791223206","volume":"23","author":"E. Grandjean","year":"1994","unstructured":"Grandjean, E.: Linear time algorithms and NP-complete problems. SIAM Journal on Computing\u00a023(3), 573\u2013597 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"93_CR10","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02127798","volume":"16","author":"E. Grandjean","year":"1996","unstructured":"Grandjean, E.: Sorting, linear time, and the satisfiability problem. Annals of Mathematics and Artificial Intelligence\u00a016, 183\u2013236 (1996)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"1","key":"93_CR11","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/PL00001594","volume":"7","author":"E. Grandjean","year":"1998","unstructured":"Grandjean, E., Olive, F.: Monadic logical definability of nondeterministic linear time. Computational Complexity\u00a07(1), 54\u201397 (1998); Journal version of CSL 1994 paper","journal-title":"Computational Complexity"},{"issue":"1","key":"93_CR12","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/S0097539799360240","volume":"32","author":"E. Grandjean","year":"2002","unstructured":"Grandjean, E., Schwentick, T.: Machine-independent characterizations and complete problems for deterministic linear time. SIAM Journal on Computing\u00a032(1), 196\u2013230 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"93_CR13","unstructured":"Grohe, M.: The structure of fixed-point logics. PhD thesis, Albert-Ludwigs Universit\u00e4t Freiburg, Germany (1994)"},{"key":"#cr-split#-93_CR14.1","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schweikardt, N.: Comparing the succinctness of monadic query languages over finite trees. Technical Report EDI-INF-RR-0168, School of Informatics, University of Edinburgh, Scotland, U.K (2003);","DOI":"10.1007\/978-3-540-45220-1_20"},{"key":"#cr-split#-93_CR14.2","unstructured":"Full version of CSL 2003 paper"},{"key":"93_CR15","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1145\/343369.343386","volume":"1","author":"M. Grohe","year":"2000","unstructured":"Grohe, M., Schwentick, T.: Locality of order-invariant first-order formulas. ACM Transactions on Computational Logic\u00a01, 112\u2013130 (2000); Journal version of MFCS 1998 paper","journal-title":"ACM Transactions on Computational Logic"},{"key":"93_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, Heidelberg (1999)"},{"key":"93_CR17","volume-title":"IBM Symposium 1972, Complexity of Computers Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: IBM Symposium 1972, Complexity of Computers Computations, Plenum Press, NewYork (1972)"},{"key":"93_CR18","unstructured":"Lindell, S.: Linear-time algorithms for monadic logic. In: Short presentation at the 18th IEEE Symposium on Logic in Computer Science, LICS 2003 (2003)"},{"key":"93_CR19","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01786976","volume":"15","author":"J.F. Lynch","year":"1982","unstructured":"Lynch, J.F.: Complexity classes and theories of finite models. Mathematical Systems Theory\u00a015, 127\u2013144 (1982)","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"93_CR20","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/inco.2002.2955","volume":"179","author":"O. Matz","year":"2002","unstructured":"Matz, O., Schweikardt, N., Thomas, W.: The monadic quantifier alternation hierarchy over grids and graphs. Information and Computation\u00a0179(2), 356\u2013383 (2002)","journal-title":"Information and Computation"},{"key":"93_CR21","unstructured":"More, M., Olive, F.: Rudimentary languages and second-order logic. Technical Report 1996-1, Universit\u00e9 de Caen, France (1996)"},{"key":"93_CR22","doi-asserted-by":"crossref","unstructured":"Rossman, B.: Successor-invariance in the finite. In: Proceedings of the 18th IEEE Symposium on Logic in Computer Science, LICS 2003 (2003)","DOI":"10.1109\/LICS.2003.1210054"},{"key":"93_CR23","doi-asserted-by":"crossref","unstructured":"Schweikardt, N.: On the expressive power of monadic least fixed point logic. Full version of ICALP 2004 paper, Available at http:\/\/www.informatik.hu-berlin.de\/~schweika\/publications.html","DOI":"10.1007\/978-3-540-27836-8_93"},{"key":"93_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/10703163_2","volume-title":"Computer Science Logic","author":"T. Schwentick","year":"1999","unstructured":"Schwentick, T.: Descriptive complexity, lower bounds and linear time. In: Gottlob, G., Grandjean, E., Seyr, K. (eds.) CSL 1998. LNCS, vol.\u00a01584, pp. 9\u201328. Springer, Heidelberg (1999)"},{"key":"93_CR25","volume-title":"Handbook of Formal Languages","author":"W. Thomas","year":"1996","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a03, Springer, Heidelberg (1996)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_93.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,10]],"date-time":"2021-11-10T01:30:50Z","timestamp":1636507850000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_93"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_93","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}