{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:01Z","timestamp":1725488941926},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74456-6_15","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"147-158","source":"Crossref","is-referenced-by-count":6,"title":["Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Behle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Mercer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC\n                  1. J. Comp. System Sci.\u00a038, 150\u2013164 (1989)","journal-title":"J. Comp. System Sci."},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.A. Barrington","year":"1990","unstructured":"Barrington, D.A., Immerman, N., Straubing, H.: On uniformity within NC\n                  1. J. Comp. System Sci.\u00a041, 274\u2013306 (1990)","journal-title":"J. Comp. System Sci."},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1109\/LICS.2001.932496","volume-title":"Proc. of the 16th IEEE Symposium On Logic in Computer Science","author":"D. Barrington","year":"2001","unstructured":"Barrington, D., Immerman, N., Lautemann, C., Schweickardt, N., Th\u00e9rien, D.: The Crane Beach Conjecture. In: Proc. of the 16th IEEE Symposium On Logic in Computer Science, pp. 187\u2013196. IEEE Computer Society Press, Los Alamitos (2001)"},{"issue":"4","key":"15_CR4","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. Barrington","year":"1988","unstructured":"Barrington, D., Th\u00e9rien, D.: Finite Monoids and the Fine Structure of NC\n                  1. Journal of ACM\u00a035(4), 941\u2013952 (1988)","journal-title":"Journal of ACM"},{"key":"15_CR5","unstructured":"Behle, C., Krebs, A., Reifferscheid, S.: A\n                  5 not in FO+MOD+MAJ2[reg], \n                    \n                      http:\/\/www-fs.informatik.uni-tuebingen.de\/publi\/a5notinltc0.pdf\n                    \n                    \n                   (to appear)"},{"key":"15_CR6","unstructured":"Behle, C., Lange, K.-J.: FO[\u2009<\u2009]-Uniformity. In: IEEE Conference on Compuatational Complexity (2006)"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Furst, M., Saxe, J.B., Sipser, M.: Parity circuits and the polynomial-time hierarchy. In: Proc. 22th IEEE Symposium on Foundations of Computer Science, pp. 260\u2013270 (1981)","DOI":"10.1109\/SFCS.1981.35"},{"key":"15_CR8","unstructured":"Krebs, A., Lange, K.-J., Reifferscheid, St.: In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, Springer, Heidelberg (2005)"},{"key":"15_CR9","unstructured":"Kouck\u00fd, M., Lautemann, C., Poloczek, S., Th\u00e9rien, D.: Circuit lower bounds via Ehrenfeucht-Frai\u0307ss\u00e9 games. In: Proc. 21st Conf. on Compuatational Complexity (CCC\u201906) (2006)"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1109\/CCC.2004.1313817","volume-title":"Proc. of the 19th IEEE Conference on Computational Complexity","author":"K.-J. Lange","year":"2004","unstructured":"Lange, K.-J.: Some results on majority quantifiers over words. In: Proc. of the 19th IEEE Conference on Computational Complexity, pp. 123\u2013129. IEEE Computer Society Press, Los Alamitos (2004)"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1006\/jcss.2000.1742","volume":"62","author":"C. Lautemann","year":"2001","unstructured":"Lautemann, C., McKenzie, P., Schwentick, T., Vollmer, H.: The descriptive complexity approach to LOGCFL. J. Comp. System Sci.\u00a062, 629\u2013652 (2001)","journal-title":"J. Comp. System Sci."},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Lawson, M.: Finite Automata. Chapman & Hall\/CRC (2004)","DOI":"10.1201\/9781482285840"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0022-4049(89)90137-0","volume":"62","author":"J. Rhodes","year":"1989","unstructured":"Rhodes, J., Tilson, B.: The Kernel of Monoid Morphisms. J. Pure Applied Alg.\u00a062, 227\u2013268 (1989)","journal-title":"J. Pure Applied Alg."},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_40","volume-title":"STACS 2006","author":"A. Roy","year":"2006","unstructured":"Roy, A., Straubing, H.: Definability of Languages by Generalized First-Order Formulas over (N,+). In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, Springer, Heidelberg (to appear 2006)"},{"key":"15_CR15","first-page":"326","volume-title":"Proc. of 14th IEEE Symposium On Logic in Computer Science","author":"M. Ruhl","year":"1999","unstructured":"Ruhl, M.: Counting and addition cannot express deterministic transitive closure. In: Proc. of 14th IEEE Symposium On Logic in Computer Science, pp. 326\u2013334. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"15_CR16","unstructured":"Schweikardt, N.: On the Expressive Power of First-Order Logic with Built-In Predicates. In: Dissertation, Universit\u00e4t Mainz (2001)"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user (1994)","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"15_CR18","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 by generalize quantifiers. Information and Computation\u00a0118, 289\u2013301 (1995)","journal-title":"Information and Computation"},{"key":"15_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/3-540-44693-1_48","volume-title":"STACS 2001","author":"H. Straubing","year":"2001","unstructured":"Straubing, H., Th\u00e9rien, D.: Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 551\u2013562. Springer, Heidelberg (2001)"},{"key":"15_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-45995-2_13","volume-title":"LATIN 2002: Theoretical Informatics","author":"H. Straubing","year":"2002","unstructured":"Straubing, H., Th\u00e9rien, D.: Weakly Iterated Block Products of Finite Monoids. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 91\u2013104. Springer, Heidelberg (2002)"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Th\u00e9rien, D., Wilke, T.: Over Words, Two Variables are as Powerful as One Quantifier Alternation. In: Proc. 30th ACM Symposium on the Theory of Computing, pp. 256\u2013263 (1998)","DOI":"10.1145\/276698.276749"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T01:12:18Z","timestamp":1558487538000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540744559","9783540744566"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}