{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:41:29Z","timestamp":1742928089347,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540875307"},{"type":"electronic","value":"9783540875314"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87531-4_7","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T08:40:53Z","timestamp":1220085653000},"page":"64-78","source":"Crossref","is-referenced-by-count":0,"title":["Extensional Uniformity for Boolean Circuits"],"prefix":"10.1007","author":[{"given":"Pierre","family":"McKenzie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Thomas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1145\/76359.76370","volume":"36","author":"E. Allender","year":"1989","unstructured":"Allender, E.: P-uniform circuit complexity. Journal of the Association for Computing Machinery\u00a036, 912\u2013928 (1989)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proc. of the 16th Annual ACM Symposium on Theory of Computing, pp. 202\u2013211 (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1109\/SCT.1994.315806","volume-title":"Proceedings 9th Structure in Complexity Theory","author":"D.A. Mix Barrington","year":"1994","unstructured":"Mix Barrington, D.A., Immerman, N.: Time, hardware, and uniformity. In: Proceedings 9th Structure in Complexity Theory, pp. 176\u2013185. IEEE Computer Society Press, Los Alamitos (1994)"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.jcss.2004.07.004","volume":"70","author":"D.A. Mix Barrington","year":"2005","unstructured":"Mix Barrington, D.A., Immerman, N., Lautemann, C., Schweikardt, N., Th\u00e9rien, D.: First-order expressibility of languages with neutral letters or: The Crane Beach Conjecture. Journal of Computer and System Sciences\u00a070, 101\u2013127 (2005)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.A. Mix Barrington","year":"1990","unstructured":"Mix Barrington, D.A., Immerman, N., Straubing, H.: On uniformity within NC1. Journal of Computer and System Sciences\u00a041(3), 274\u2013306 (1990)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Behle, C., Lange, K.-J.: FO[<]-Uniformity. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), pp. 183\u2013189 (2006)","DOI":"10.1109\/CCC.2006.20"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Leitf\u00e4den der angewandten Mathematik und Mechanik LAMM, vol.\u00a038. Teubner (1979)","DOI":"10.1007\/978-3-663-09367-1"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"Borodin, A.: On relating time and space to size and depth. SIAM Journal on Computing\u00a06, 733\u2013744 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR9","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Ginsburg, S., Greibach, S., Hopcroft, J.: Abstract families of languages. Memoirs of the Amer. Math. Soc.\u00a087 (1969)","DOI":"10.1090\/memo\/0087"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(88)90047-6","volume":"29","author":"O. Ibarra","year":"1988","unstructured":"Ibarra, O., Jiang, T., Ravikumar, B.: Some subclasses of context-free languages in NC1. Information Processing Letters\u00a029, 111\u2013117 (1988)","journal-title":"Information Processing Letters"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"Immerman, N.: Expressibility and parallel complexity. SIAM Journal on Computing\u00a018, 625\u2013638 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR13","first-page":"191","volume":"28","author":"R. Karp","year":"1982","unstructured":"Karp, R., Lipton, R.: Turing machines that take advice. L\u2019enseignement math\u00e9matique\u00a028, 191\u2013209 (1982)","journal-title":"L\u2019enseignement math\u00e9matique"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BFb0015925","volume-title":"Machines, Languages, and Complexity","author":"K.-J. Lange","year":"1989","unstructured":"Lange, K.-J.: Complexity theory and formal languages. In: Dassow, J., Kelemen, J. (eds.) IMYCS 1988. LNCS, vol.\u00a0381, pp. 19\u201336. Springer, Heidelberg (1989)"},{"key":"7_CR15","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"},{"issue":"4","key":"7_CR16","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. Journal of Computer and Systems Sciences\u00a062(4), 629\u2013652 (2001)","journal-title":"Journal of Computer and Systems Sciences"},{"key":"7_CR17","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","volume":"32","author":"P. Lindstr\u00f6m","year":"1966","unstructured":"Lindstr\u00f6m, P.: First order predicate logic with generalized quantifiers. Theoria\u00a032, 186\u2013195 (1966)","journal-title":"Theoria"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF01762237","volume":"7","author":"L. Liu","year":"1973","unstructured":"Liu, L., Weiner, P.: An infinite hierarchy of intersections of context-free languages. Mathematical Systems Theory\u00a07, 185\u2013192 (1973)","journal-title":"Mathematical Systems Theory"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"21","author":"W.L. Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: On uniform circuit complexity. Journal of Computer and Systems Sciences\u00a021, 365\u2013383 (1981)","journal-title":"Journal of Computer and Systems Sciences"},{"issue":"3","key":"7_CR20","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":"7_CR21","doi-asserted-by":"crossref","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. Birkh\u00e4user, Boston (1994)"},{"key":"7_CR22","series-title":"Texts in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity \u2013 A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity \u2013 A Uniform Approach. Texts in Theoretical Computer Science. Springer, Heidelberg (1999)"},{"key":"7_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/978-3-662-41148-3_11","volume-title":"3. GI Jahrestagung","author":"D. Wotschke","year":"1973","unstructured":"Wotschke, D.: The Boolean closure of the deterministic and nondeterministic context-free languages. In: GI 1973. LNCS, vol.\u00a01, pp. 113\u2013121. Springer, Heidelberg (1973)"},{"issue":"2","key":"7_CR24","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0207018","volume":"7","author":"C. Wrathall","year":"1978","unstructured":"Wrathall, C.: Rudimentary predicates and relative computation. SIAM Journal on Computing\u00a07(2), 194\u2013209 (1978)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87531-4_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T19:04:31Z","timestamp":1738350271000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87531-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540875307","9783540875314"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87531-4_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}