{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:56:26Z","timestamp":1725544586742},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540323013"},{"type":"electronic","value":"9783540322887"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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":[[2006]]},"DOI":"10.1007\/11672142_40","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T08:27:54Z","timestamp":1141115274000},"page":"489-499","source":"Crossref","is-referenced-by-count":3,"title":["Definability of Languages by Generalized First-Order Formulas over (N,+)"],"prefix":"10.1007","author":[{"given":"Amitabha","family":"Roy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Howard","family":"Straubing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. Mix Barrington","year":"1989","unstructured":"Mix Barrington, D.: Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC 1. J. Comp. Syst. Sci.\u00a038, 150\u2013164 (1989)","journal-title":"J. Comp. Syst. Sci."},{"key":"40_CR2","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"D. Mix Barrington","year":"1992","unstructured":"Mix Barrington, D., Compton, K., Straubing, H., Th\u00e9rien, D.: Regular Languages in NC 1. J. Comp. Syst. Sci.\u00a044, 478\u2013499 (1992)","journal-title":"J. Comp. Syst. Sci."},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. Mix Barrington","year":"1990","unstructured":"Mix Barrington, D., Immerman, N., Straubing, H.: On Uniformity in NC 1. J. Comp. Syst. Sci.\u00a041, 274\u2013306 (1990)","journal-title":"J. Comp. Syst. Sci."},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Barrington, D.M., Immerman, N., Lautemann, C., Schweikardt, N., Th\u00e9rien, D.: The Crane Beach Conjecture. In: LICS 2001, 187-196 (2001)","DOI":"10.1109\/LICS.2001.932496"},{"key":"40_CR5","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1006\/jcss.1995.1029","volume":"50","author":"D. Mix Barrington","year":"1995","unstructured":"Mix Barrington, D., Straubing, H.: Superlinear Lower Bounds for Bounded-Width Branching Programs. J. Comp. Syst. Sci.\u00a050, 374\u2013381 (1995)","journal-title":"J. Comp. Syst. Sci."},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0890-5401(90)90007-5","volume":"89","author":"D. Mix Barrington","year":"1990","unstructured":"Mix Barrington, D., Straubing, H., Th\u00e9rien, D.: Nonuniform Automata over Groups. Information and Computation\u00a089, 109\u2013132 (1990)","journal-title":"Information and Computation"},{"key":"40_CR7","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. Mix Barrington","year":"1988","unstructured":"Mix Barrington, D., Th\u00e9rien, D.: Finite Monoids and the Fine Structure of NC 1. JACM\u00a035, 941\u2013952 (1988)","journal-title":"JACM"},{"issue":"4","key":"40_CR8","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1145\/347476.347477","volume":"47","author":"M. Benedikt","year":"2000","unstructured":"Benedikt, M., Libkin, L.: Relational Queries over Interpreted Structures. Journal of the ACM\u00a047(4), 644\u2013680 (2000)","journal-title":"Journal of the ACM"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Lange, K.-J.: Some Results on Majority Quantifiers over Words. In: 19th IEEE Conference on Computational Complexity, pp. 123\u2013129 (2004)","DOI":"10.1109\/CCC.2004.1313817"},{"key":"40_CR10","volume-title":"Finite Model Theory and its Applications","author":"L. Libkin","year":"2005","unstructured":"Libkin, L.: Embedded finite models and constraint databases. In: Gr\u00e4del, E., et al. (eds.) Finite Model Theory and its Applications, Springer, New York (2005)"},{"key":"40_CR11","doi-asserted-by":"publisher","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, New York (2004)"},{"key":"40_CR12","doi-asserted-by":"publisher","first-page":"659","DOI":"10.2307\/2273595","volume":"47","author":"J.F. Lynch","year":"1982","unstructured":"Lynch, J.F.: On Sets of Relations Definable by Addition. J. Symbolic Logic\u00a047, 659\u2013668 (1982)","journal-title":"J. Symbolic Logic"},{"key":"40_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1999.2842","volume":"160","author":"J. Nurmonen","year":"2000","unstructured":"Nurmonen, J.: Counting Modulo Quantifiers on Finite Structures. Information and Computation\u00a0160, 183\u2013207 (2000)","journal-title":"Information and Computation"},{"key":"40_CR14","unstructured":"Presburger, M.: Ueber die Vollstaendigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Comptes Rendus du I congr\u00e8s de Math\u00e9maticiens des Pays Slaves, Warsaw, Poland, pp. 92\u2013101 (1929)"},{"key":"40_CR15","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"Razborov, A.A.: Lower Bounds for the Size of Circuits of Bounded Depth with Basis {\u2009\u2227\u2009,\u2009\u2295\u2009}. Math. Notes of the Soviet Academy of Sciences\u00a041, 333\u2013338 (1987)","journal-title":"Math. Notes of the Soviet Academy of Sciences"},{"issue":"3","key":"40_CR16","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"},{"key":"40_CR17","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In: Proc. 19th ACM STOC, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"40_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic and Circuit Complexity","author":"H. Straubing","year":"1994","unstructured":"Straubing, H.: Finite Automata, Formal Logic and Circuit Complexity. Birkha\u00fcser, Boston (1994)"},{"key":"40_CR19","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/inco.1995.1067","volume":"118","author":"H. Straubing","year":"1995","unstructured":"Straubing, H., Th\u00e9rien, D., Thomas, W.: Regular Languages Defined with Generalized Quantifiers. Information and Computation\u00a0118, 289\u2013301 (1995)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T03:31:21Z","timestamp":1555471881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11672142_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}