{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:08:44Z","timestamp":1725516524545},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642326202"},{"type":"electronic","value":"9783642326219"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32621-9_6","type":"book-chapter","created":{"date-parts":[[2012,8,18]],"date-time":"2012-08-18T06:40:40Z","timestamp":1345272040000},"page":"85-87","source":"Crossref","is-referenced-by-count":1,"title":["On the Expressive Power of Logics with Invariant Uses of Arithmetic Predicates"],"prefix":"10.1007","author":[{"given":"Nicole","family":"Schweikardt","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-642-22012-8_29","volume-title":"Automata, Languages and Programming","author":"M. Anderson","year":"2011","unstructured":"Anderson, M., van Melkebeek, D., Schweikardt, N., Segoufin, L.: Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 368\u2013379. Springer, Heidelberg (2011)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Anderson, M., van Melkebeek, D., Schweikardt, N., Segoufin, L.: Locality from circuit lower bounds. To appear in SIAM Journal on Computing (2012)","DOI":"10.1137\/110856873"},{"issue":"1","key":"6_CR3","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 on Symbolic Logic\u00a074(1), 168\u2013186 (2009)","journal-title":"Journal on Symbolic Logic"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The Monadic Second-Order Logic of Graphs X: Linear Orderings. Theoretical Computer Science\u00a0160(1&2), 87\u2013143","DOI":"10.1016\/0304-3975(95)00083-6"},{"key":"6_CR5","unstructured":"Ganzow, T., Rubin, S.: Order-invariant MSO is stronger than Counting MSO in the finite. In: Proc. 25th Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 313\u2013324 (2008)"},{"issue":"1","key":"6_CR6","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"},{"key":"6_CR7","unstructured":"Harwath, F., Schweikardt, N.: Regular tree languages, cardinality predicates, and addition-invariant FO. In: Proc. 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). LIPIcs, vol.\u00a014, pp. 489\u2013500 (2012)"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/BFb0028596","volume-title":"STACS 98","author":"D. Lapoire","year":"1998","unstructured":"Lapoire, D.: Recognizability Equals Monadic Second-Order Definability for Sets of Graphs of Bounded Tree-Width. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 618\u2013628. Springer, Heidelberg (1998)"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer (2004)","DOI":"10.1007\/978-3-662-07003-1"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-63385-5_43","volume-title":"Computational Logic and Proof Theory","author":"J.A. Makowsky","year":"1997","unstructured":"Makowsky, J.A.: Invariant Definability (Extended Abstract). In: Gottlob, G., Leitsch, A., Mundici, D. (eds.) KGC 1997. LNCS, vol.\u00a01289, pp. 186\u2013202. Springer, Heidelberg (1997)"},{"key":"6_CR11","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)"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1002\/malq.19970430315","volume":"43","author":"M. More","year":"1997","unstructured":"More, M., Olive, F.: Rudimentary languages and second order logic. Mathematical Logic Quarterly\u00a043, 419\u2013426 (1997)","journal-title":"Mathematical Logic Quarterly"},{"issue":"4","key":"6_CR13","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"},{"issue":"2","key":"6_CR14","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"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Rossman, B.: On the constant-depth complexity of k-clique. In: Proc. 40th Annual ACM Symposium on the Theory of Computing (STOC 2008), pp. 721\u2013730. ACM (2008)","DOI":"10.1145\/1374376.1374480"},{"issue":"2-3","key":"6_CR16","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":"6_CR17","doi-asserted-by":"crossref","unstructured":"Schweikardt, N., Segoufin, L.: Addition-invariant FO and regularity. In: Proc. 25th IEEE Symposium on Logic in Computer Science (LICS), pp. 273\u2013282 (2010)","DOI":"10.1109\/LICS.2010.16"}],"container-title":["Lecture Notes in Computer Science","Logic, Language, Information and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32621-9_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T23:25:40Z","timestamp":1557185140000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32621-9_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642326202","9783642326219"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32621-9_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}