{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:29:13Z","timestamp":1725456553178},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540513711"},{"type":"electronic","value":"9783540462019"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/bfb0035785","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T09:00:28Z","timestamp":1133427628000},"page":"589-602","source":"Crossref","is-referenced-by-count":7,"title":["Automata theory meets circuit complexity"],"prefix":"10.1007","author":[{"given":"P.","family":"McKenzie","sequence":"first","affiliation":[]},{"given":"D.","family":"Th\u00e9rien","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,11,29]]},"reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, \u03a3 1 1 formulae on finite structures, Annals of Pure and Applied Logic24 (1983), pp. 1\u201348.","journal-title":"Annals of Pure and Applied Logic"},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"D.A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Proc. of the 18th ACM Symp. on the Theory of Computing (1986), pp. 1\u20135.","DOI":"10.1145\/12130.12131"},{"key":"38_CR3","unstructured":"D. Mix Barrington, K. Compton, H. Straubing and D. Th\u00e9rien, Regular languages in NC1, Boston College Technical Report TR-BCCS-88-02, 1988."},{"key":"38_CR4","unstructured":"D. Mix Barrington, N. Immerman and H. Straubing, On uniformity within NC1, Proc. of the 3rd Annual Conf. on the Structure in Complexity Theory, IEEE Computer Society Press (1988), pp. 47\u201359."},{"key":"38_CR5","unstructured":"D.A. Barrington, H. Straubing and D. Th\u00e9rien, unpublished manuscript, 1988."},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"D.A. Barrington and D. Th\u00e9rien, Finite monoids and the fine structure of NC1, Proc. of the 19th ACM Symp. on the Theory of Computing (1987), pp. 101\u2013109.","DOI":"10.1145\/28395.28407"},{"key":"38_CR7","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/3-540-18088-5_13","volume":"267","author":"D.A. Barrington","year":"1987","unstructured":"D.A. Barrington and D. Th\u00e9rien, Non-uniform automata over groups, Proc. of the 14th International Colloquium on Automata, Languages and Programming, Springer Lecture Notes in Comp. Sci. 267 (1987), pp. 163\u2013173.","journal-title":"Springer Lecture Notes in Comp. Sci."},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"A. Borodin, D. Dolev, F. Fich and W. Paul, Bounds for width-two branching programs, Proc. of the 15th ACM Symp. on the Theory of Computing (1983), pp. 97\u201393.","DOI":"10.1145\/800061.808736"},{"key":"38_CR9","first-page":"2","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"S.A. Cook, A taxonomy of problems with fast parallel solutions, Information and Computation64 (1985), pp. 2\u201322.","journal-title":"Information and Computation"},{"key":"38_CR10","unstructured":"S. Eilenberg, Automata, Languages and Machines, Academic Press, Vol. A (1974), Vol. B, (1976)."},{"key":"38_CR11","first-page":"260","volume":"18","author":"M.L. Furst","year":"1984","unstructured":"M.L. Furst, J.B. Saxe and M. Sipser, Parity, circuits, and the polynomial-time hierarchy, Proc. of the 22nd IEEE Symp. on the Foundations of Computer Science (1981), pp. 260\u2013270. Journal version Math. Systems Theory18 (1984), 13\u201327.","journal-title":"Journal version Math. Systems Theory"},{"key":"38_CR12","unstructured":"J.T. H\u00e5stad, Computational Limitations for Small-Depth Circuits, Ph. D. Thesis, M.I.T., ACM Doctoral Dissertation Awards, MIT Press (1987)."},{"key":"38_CR13","unstructured":"J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley (1979)."},{"issue":"2","key":"38_CR14","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0196-6774(86)90011-8","volume":"7","author":"D.S. Johnson","year":"1986","unstructured":"D.S. Johnson, The NP-completeness column: and ongoing guide, J. of Algorithms7:2 (June 1986), pp. 289\u2013305.","journal-title":"J. of Algorithms"},{"key":"38_CR15","first-page":"3","volume-title":"Automata Studies","author":"S.C. Kleene","year":"1954","unstructured":"S.C. Kleene, Representation of events in nerve nets and finite automata, Automata Studies, (Shannon and McCarthy, eds), Princeton University Press, Princeton (1954), pp 3\u201341."},{"key":"38_CR16","unstructured":"J. Mullins, Programmes sur des petites vari\u00e9t\u00e9s de mono\u00efdes ap\u00e9riodiques, M\u00e9moire de ma\u00eetrise, D\u00e9p. I.R.O., Univ. de Montr\u00e9al, en pr\u00e9paration (1988)."},{"key":"38_CR17","unstructured":"P. P\u00e9ladeau, Classes of boolean circuits and varieties of finite monoids, draft, May 1988."},{"key":"38_CR18","unstructured":"J.-E. Pin, Vari\u00e9t\u00e9s de langages formels, Masson (1984)."},{"key":"38_CR19","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0022-4049(88)90097-7","volume":"52","author":"J.-E. Pin","year":"1988","unstructured":"J.-E. Pin, H. Straubing and D. Th\u00e9rien, Locally trivial categories and unambiguous concatenation, J. of Pure and Applied Algebra52 (1988), pp. 297\u2013311.","journal-title":"J. of Pure and Applied Algebra"},{"issue":"4","key":"38_CR20","first-page":"598","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"A.A. Razborov, Lower bounds for the size of circuits of bounded depth with basis {&, \u2295}, Mathematicheskie Zametki41:4 (April 1987), 598\u2013607 (in Russian). English translation Mathematical Notes of the Academy of Sciences of the USSR41:4 (Sept. 1987), pp. 333\u2013338.","journal-title":"Mathematicheskie Zametki"},{"key":"38_CR21","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M.P. Sch\u00fctzenberger","year":"1965","unstructured":"M.P. Sch\u00fctzenberger, On finite monoids having only trivial subgroups, Information and Control8 (1965), pp. 190\u2013194.","journal-title":"Information and Control"},{"key":"38_CR22","unstructured":"I. Simon, Hierarchies of events of dot-depth one, Ph. D. Thesis, University of Waterloo (1972)."},{"key":"38_CR23","doi-asserted-by":"crossref","unstructured":"M. Sipser, Borel sets and circuit complexity, Proc. of the 15th ACM Symp. on the Theory of Computing (1983), pp. 61\u201369.","DOI":"10.1145\/800061.808733"},{"key":"38_CR24","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proc. of the 19th ACM Symp. on the Theory of Computing (1987), pp. 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"38_CR25","unstructured":"H. Straubing, Varieties of recognizable sets whose syntactic monoids contain solvable groups, Ph. D. Thesis, University of California at Berkeley (1978)."},{"key":"38_CR26","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0304-3975(81)90057-8","volume":"14","author":"D. Th\u00e9rien","year":"1981","unstructured":"D. Th\u00e9rien, Classification of finite monoids: the language approach, Theoretical Computer Science14 (1981), pp. 195,208.","journal-title":"Theoretical Computer Science"},{"key":"38_CR27","doi-asserted-by":"crossref","unstructured":"D. Th\u00e9rien, Subword counting and nilpotent groups, in Combinatorics on Words: Progress and Perspectives (L.J. Cummings ed.), Academic Press (1983), pp. 297\u2013305.","DOI":"10.1016\/B978-0-12-198820-3.50021-8"},{"key":"38_CR28","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. of the 26th IEEE Symp. on the Foundations of Computer Science (1985), pp. 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0035785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T16:32:04Z","timestamp":1554741124000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0035785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540513711","9783540462019"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/bfb0035785","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}