{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T16:59:21Z","timestamp":1725728361851},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_10","type":"book-chapter","created":{"date-parts":[[2013,6,2]],"date-time":"2013-06-02T21:03:04Z","timestamp":1370206984000},"page":"112-126","source":"Crossref","is-referenced-by-count":9,"title":["A Short Tutorial on Order-Invariant First-Order Logic"],"prefix":"10.1007","author":[{"given":"Nicole","family":"Schweikardt","sequence":"first","affiliation":[]}],"member":"297","reference":[{"unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995)","key":"10_CR1"},{"issue":"6","key":"10_CR2","doi-asserted-by":"publisher","first-page":"1481","DOI":"10.1137\/110856873","volume":"41","author":"M. Anderson","year":"2012","unstructured":"Anderson, M., van Melkebeek, D., Schweikardt, N., Segoufin, L.: Locality from circuit lower bounds. SIAM Journal on Computing\u00a041(6), 1481\u20131523 (2012)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge Univ. Press (2009)","key":"10_CR3","DOI":"10.1017\/CBO9780511804090"},{"issue":"1","key":"10_CR4","doi-asserted-by":"publisher","first-page":"168","DOI":"10.2178\/jsl\/1231082307","volume":"74","author":"M. Benedikt","year":"2009","unstructured":"Benedikt, M., Segoufin, L.: Towards a characterization of order-invariant queries over tame structures. Journal of Symbolic Logic\u00a074(1), 168\u2013186 (2009)","journal-title":"Journal of Symbolic Logic"},{"issue":"1&2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0304-3975(95)00083-6","volume":"160","author":"B. Courcelle","year":"1996","unstructured":"Courcelle, B.: The monadic second-order logic of graphs X: Linear orderings. Theoretical Computer Science\u00a0160(1&2), 87\u2013143 (1996)","journal-title":"Theoretical Computer Science"},{"unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite model theory. Springer (1999)","key":"10_CR6"},{"unstructured":"Ganzow, T., Rubin, S.: Order-invariant MSO is stronger than Counting MSO in the finite. In: Proc. STACS 2008, pp. 313\u2013324 (2008)","key":"10_CR7"},{"issue":"1","key":"10_CR8","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(1), 112\u2013130 (2000)","journal-title":"ACM Transactions on Computational Logic"},{"unstructured":"Harwath, F., Schweikardt, N.: Regular tree languages, cardinality predicates, and addition-invariant FO. In: Proc. STACS 2012, pp. 489\u2013500 (2012)","key":"10_CR9"},{"unstructured":"H\u00e5stad, J.: Computational limitations for small-depth circuits. PhD thesis. MIT (1986)","key":"10_CR10"},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.2307\/2586810","volume":"64","author":"L. Hella","year":"1999","unstructured":"Hella, L., Libkin, L., Nurmonen, J.: Notions of locality and their logical characterizations over finite models. Journal of Symbolic Logic\u00a064(4), 1751\u20131773 (1999)","journal-title":"Journal of Symbolic Logic"},{"issue":"1-3","key":"10_CR12","doi-asserted-by":"publisher","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. Information and Control\u00a068(1-3), 86\u2013104 (1986)","journal-title":"Information and Control"},{"issue":"4","key":"10_CR13","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages that capture complexity classes. SIAM Journal on Computing\u00a016(4), 760\u2013778 (1987)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer (2004)","key":"10_CR14","DOI":"10.1007\/978-3-662-07003-1"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/10703163_10","volume-title":"Computer Science Logic","author":"J.A. Makowsky","year":"1999","unstructured":"Makowsky, J.A.: Invariant Definability and P\/poly. In: Gottlob, G., Grandjean, E., Seyr, K. (eds.) CSL 1998. LNCS, vol.\u00a01584, pp. 142\u2013158. Springer, Heidelberg (1999)"},{"unstructured":"Niemist\u00f6, H.: On locality and uniform reduction. In: Proc. LICS 2005, pp. 41\u201350 (2005)","key":"10_CR16"},{"issue":"4","key":"10_CR17","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.2307\/2695073","volume":"65","author":"M. Otto","year":"2000","unstructured":"Otto, M.: Epsilon-logic is more expressive than first-order logic over finite structures. Journal of Symbolic Logic\u00a065(4), 1749\u20131757 (2000)","journal-title":"Journal of Symbolic Logic"},{"unstructured":"Potthoff, A.: Logische Klassifizierung regul\u00e4rer Baumsprachen. PhD thesis, Christian-Albrechts-Universit\u00e4t Kiel (1994)","key":"10_CR18"},{"issue":"2","key":"10_CR19","doi-asserted-by":"publisher","first-page":"601","DOI":"10.2178\/jsl\/1185803625","volume":"72","author":"B. Rossman","year":"2007","unstructured":"Rossman, B.: Successor-invariant first-order logic on finite structures. Journal of Symbolic Logic\u00a072(2), 601\u2013618 (2007)","journal-title":"Journal of Symbolic Logic"},{"doi-asserted-by":"crossref","unstructured":"Rossman, B.: On the constant-depth complexity of k-clique. In: Proc. STOC 2008, pp. 721\u2013730 (2008)","key":"10_CR20","DOI":"10.1145\/1374376.1374480"},{"issue":"3","key":"10_CR21","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/1071596.1071602","volume":"6","author":"N. Schweikardt","year":"2005","unstructured":"Schweikardt, N.: Arithmetic, first-order logic, and counting quantifiers. ACM Transactions on Computational Logic\u00a06(3), 634\u2013671 (2005)","journal-title":"ACM Transactions on Computational Logic"},{"issue":"2-3","key":"10_CR22","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.tcs.2005.10.025","volume":"350","author":"N. Schweikardt","year":"2006","unstructured":"Schweikardt, N.: On the expressive power of monadic least fixed point logic. Theoretical Computer Science\u00a0350(2-3), 325\u2013344 (2006)","journal-title":"Theoretical Computer Science"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-32621-9_6","volume-title":"Logic, Language, Information and Computation","author":"N. Schweikardt","year":"2012","unstructured":"Schweikardt, N.: On the expressive power of logics with invariant uses of arithmetic predicates. In: Ong, L., de Queiroz, R. (eds.) WoLLIC 2012. LNCS, vol.\u00a07456, pp. 85\u201387. Springer, Heidelberg (2012)"},{"doi-asserted-by":"crossref","unstructured":"Schweikardt, N., Segoufin, L.: Addition-invariant FO and regularity. In: Proc. LICS 2010, pp. 273\u2013282 (2010)","key":"10_CR24","DOI":"10.1109\/LICS.2010.16"},{"issue":"1","key":"10_CR25","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0168-0072(95)00030-5","volume":"79","author":"T. Schwentick","year":"1996","unstructured":"Schwentick, T.: On Winning Ehrenfeucht Games and Monadic NP. Annals of Pure and Applied Logic\u00a079(1), 61\u201392 (1996)","journal-title":"Annals of Pure and Applied Logic"},{"doi-asserted-by":"crossref","unstructured":"Vardi, M.: The complexity of relational query languages. In: Proc. STOC 1982, pp. 137\u2013146 (1982)","key":"10_CR26","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T12:29:43Z","timestamp":1557750583000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}