{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:27Z","timestamp":1760202507566,"version":"3.32.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1991,12,1]],"date-time":"1991-12-01T00:00:00Z","timestamp":691545600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1991,12]]},"DOI":"10.1007\/bf01212963","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T13:00:21Z","timestamp":1109336421000},"page":"330-359","source":"Crossref","is-referenced-by-count":34,"title":["NC1: The automata-theoretic viewpoint"],"prefix":"10.1007","volume":"1","author":[{"given":"Pierre","family":"McKenzie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"P\ufffdladeau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Therien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, ? 1 1 formulae on finite structures,Ann. Pure and Applied Logic 24 (1983), 1?48.","journal-title":"Ann. Pure and Applied Logic"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. A. M. Barrington","year":"1989","unstructured":"D. A. M. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages inNC 1,J. Computer and Systems Science 38 (1989), 150?164.","journal-title":"J. Computer and Systems Science"},{"key":"CR3","unstructured":"D. A. M. Barrington, K. Compton, H. Straubing, and D. Th\u00e9rien, Regular languages inNC 1, Boston College Technical Report TR-BCCS-88-02, 1988, to appear inJ. Computer and Systems Science."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. A. M. Barrington","year":"1990","unstructured":"D. A. M. Barrington, N. Immerman, andH. Straubing, On uniformity withinNC 1,J. Computer and Systems Science 41 (1990), 274?306.","journal-title":"J. Computer and Systems Science"},{"key":"CR5","unstructured":"D. A. M. Barrington and H. Straubing, Linear-size bounded-width branching programs, Boston College Tech. Rep. BCCS 90-11, October 1990."},{"key":"CR6","unstructured":"D. A. M. Barrington, H. Straubing, and D. Th\u00e9rien, unpublished manuscript, 1988."},{"issue":"2","key":"CR7","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0890-5401(90)90007-5","volume":"89","author":"D. A. M. Barrington","year":"1990","unstructured":"D. A. M. Barrington, H. Straubing, andD. Th\u00e9rien, Nonuniform automata over groups,Inform. and Computation 89, 2 (1990), 109?132.","journal-title":"Inform. and Computation"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. A. M. Barrington","year":"1988","unstructured":"D. A. M. Barrington andD. Th\u00e9rien, Finite Monoids and the Fine Structure ofNC 1,J. Assoc Comput. Mach. 35 (1988), 941?952.","journal-title":"J. Assoc Comput. Mach."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"F. B\u00e9dard, F. Lemieux, and P. McKenzie, Extensions to Barrington'sM-program model,Proc. of the 5th Annual Structure in Complexity Theory Conf., IEEE Computer Society Press, 1990, 200?209, to appear inTheoret. Comput. Science.","DOI":"10.1109\/SCT.1990.113968"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1137\/0215040","volume":"15","author":"A. Borodin","year":"1986","unstructured":"A. Borodin, D. Dolev, F. Fich, andW. Paul, Bounds for width two branching programs,SIAM J. Comput. 15 (1986), 549?560.","journal-title":"SIAM J. Comput."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0012-365X(73)80005-6","volume":"4","author":"J. A. Brzozowski","year":"1973","unstructured":"J. A. Brzozowski andI. Simon, Characterizations of locally testable events,Discrete Mathematics 4 (1973), 243?271.","journal-title":"Discrete Mathematics"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/0022-0000(80)90003-3","volume":"20","author":"J. A. Brzozowski","year":"1980","unstructured":"J. A. Brzozowski andF. Fich, Languages ofR-trivial monoids,J. Computer and Systems Science 20 (1980), 32?49.","journal-title":"J. Computer and Systems Science"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0022-0000(78)90049-1","volume":"16","author":"J. A. Brzozowski","year":"1978","unstructured":"J. A. Brzozowski andR. Knast, The dot-depth hierarchy of star-free languages is infinite,J. Computer and Systems Science 16 (1978), 37?55.","journal-title":"J. Computer and Systems Science"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"A. Chandra, M. Furst, and R. Lipton, Multi-party protocol,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 94?99.","DOI":"10.1145\/800061.808737"},{"key":"CR15","first-page":"2","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"S.A. Cook, A taxonomy of problems with fast parallel solutions,Inform. and Computation 64 (1985), 2?22.","journal-title":"Inform. and Computation"},{"key":"CR16","unstructured":"S. Eilenberg,Automata, Languages, and Machines, Academic Press, Vol. A (1974), Vol. B (1976)."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"18","author":"M. L. Furst","year":"1984","unstructured":"M. L. Furst, J. B. Saxe, andM. Sipser, Parity, circuits, and the polynomial-time hierarchy,Math. Systems Theory 18 (1984), 13?27.","journal-title":"Math. Systems Theory"},{"key":"CR18","volume-title":"Ramsey Theory","author":"R. Graham","year":"1980","unstructured":"R. Graham, B. Rothschild, andJ. Spencer,Ramsey Theory, Wiley, New York, 1980."},{"key":"CR19","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":"CR20","unstructured":"J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0196-6774(86)90011-8","volume":"7","author":"D. S. Johnson","year":"1986","unstructured":"D. S. Johnson, TheNP-completeness column: an ongoing guide,J. Algorithms 7 (1986), 289?305.","journal-title":"J. Algorithms"},{"key":"CR22","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?41."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1137\/0218027","volume":"18","author":"K. Ko","year":"1989","unstructured":"K. Ko, Relativized polynomial time hierarchies having exactlyK levels,SIAM J. Comput. 18 (1989), 392?408.","journal-title":"SIAM J. Comput."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1090\/S0002-9947-1965-0188316-1","volume":"116","author":"K. Krohn","year":"1965","unstructured":"K. Krohn andJ. L. Rhodes, Algebraic theory of machines, I. Prime decomposition theorem for finite semigroups and machines,Trans. Amer. Math. Soc. 116 (1965), 450?464.","journal-title":"Trans. Amer. Math. Soc."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/0021-8693(87)90048-2","volume":"110","author":"S. W. Margolis","year":"1987","unstructured":"S. W. Margolis andJ.-E. Pin Inverse semigroups and varieties of finite semigroups,J. Algebra 110 (1987), 306?323.","journal-title":"J. Algebra"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/BFb0035785","volume":"372","author":"P. McKenzie","year":"1989","unstructured":"P. McKenzie andD. Th\u00e9rien, Automata theory meets circuit complexity, Proc. 16th Intern. Colloquium on Automata, Languages and Programming,Springer Lecture Notes in Comp. Sci. 372, 1989, 589?602.","journal-title":"Springer Lecture Notes in Comp. Sci."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/BF01761708","volume":"8","author":"R. McNaughton","year":"1974","unstructured":"R. McNaughton, Algebraic decision procedures for local testability,Math. Systems Theory 8 (1974), 60?76.","journal-title":"Math. Systems Theory"},{"key":"CR28","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, 1988."},{"key":"CR29","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0022-0000(88)90030-X","volume":"36","author":"I. Parberry","year":"1988","unstructured":"I. Parberry andG. Schnitger, Parallel computation with threshold functions,J. Computer and Systems Science 36 (1988), 278?302.","journal-title":"J. Computer and Systems Science"},{"key":"CR30","unstructured":"P. P\u00e9ladeau,Classes de circuits bool\u00e9ens et vari\u00e9t\u00e9s de mono\u00efdes, Ph. D. Thesis, Universit\u00e9 Paris VI, 1990."},{"key":"CR31","unstructured":"P. P\u00e9ladeau, Sur le produit avec compteur modulo un nombre premier, to appear inRevue Automatique Informatique et Recherche Op\u00e9rationnelle-Informatique Th\u00e9orique."},{"key":"CR32","unstructured":"P. P\u00e9ladeau, Formulas, regular languages and Boolean circuits, to appear inTheoret. Comput. Science A."},{"key":"CR33","doi-asserted-by":"crossref","unstructured":"N. Pippenger, On simultaneous resource bounds,Proc. 20th IEEE Ann. Symp. Foundations of Computer Science, 1979, 307?311.","DOI":"10.1109\/SFCS.1979.29"},{"key":"CR34","volume-title":"Vari\u00e9t\u00e9s de langages formels, Masson (1984)","author":"J.-E. Pin","year":"1986","unstructured":"J.-E. Pin,Vari\u00e9t\u00e9s de langages formels, Masson (1984). English version:Varieties of formal languages, Plenum, New York, 1986."},{"key":"CR35","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/BFb0015770","volume":"194","author":"J.-E. Pin","year":"1985","unstructured":"J.-E. Pin, Finite group topology andp-adic topology for free monoids, Proc. 12th Intern. Colloquium on Automata, Languages and Programming,Springer Lecture Notes in Comp. Sci. 194, 1985, 445?455.","journal-title":"Springer Lecture Notes in Comp. Sci."},{"key":"CR36","doi-asserted-by":"crossref","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, andD. Th\u00e9rien, Locally trivial categories and unambiguous concatenation,J. Pure Applied Algebra 52 (1988), 297?311.","journal-title":"J. Pure Applied Algebra"},{"issue":"4","key":"CR37","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 {&, ?}Mathematicheskie Zametki 41:4 (April 1987), 598?607 (in Russian). English translationMathematical Notes of the Academy of Sciences of the USSR 41 (1987), 333?338.","journal-title":"Mathematicheskie Zametki"},{"key":"CR38","doi-asserted-by":"crossref","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,Inform. and Control 8 (1965), 190?194.","journal-title":"Inform. and Control"},{"key":"CR39","unstructured":"I. Simon,Hierarchies of events of dot-depth one, Ph. D. Thesis, University of Waterloo, 1972."},{"key":"CR40","doi-asserted-by":"crossref","unstructured":"M. Sipser, Borel sets and circuit complexity,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 61?69.","DOI":"10.1145\/800061.808733"},{"key":"CR41","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity,Proc. 19th Ann. ACM Symp. Theory of Computing, 1987, 77?82.","DOI":"10.1145\/28395.28404"},{"key":"CR42","unstructured":"H. Straubing,Varieties of recognizable sets whose syntactic monoids contain solvable groups, Ph. D. Thesis, University of California at Berkeley, 1978."},{"key":"CR43","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1142\/S0218196791000043","volume":"1","author":"H. Straubing","year":"1991","unstructured":"H. Straubing, Constant-depth periodic circuits,Int. J. of Algebra and Computation,1 (1991), 49?88.","journal-title":"Int. J. of Algebra and Computation"},{"key":"CR44","unstructured":"D. Th\u00e9rien,Classification of regular languages by congruences, Ph. D. Thesis, University of Waterloo, 1980."},{"key":"CR45","doi-asserted-by":"crossref","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,Theoret. Comput. Science 14 (1981), 195?208.","journal-title":"Theoret. Comput. Science"},{"key":"CR46","doi-asserted-by":"crossref","unstructured":"D. Th\u00e9rien, Subword counting and nilpotent groups, inCombinatorics on Words: Progress and Perspectives (L.J. Cummings ed.), Academic Press, 1983, 297?305.","DOI":"10.1016\/B978-0-12-198820-3.50021-8"},{"key":"CR47","unstructured":"P. Weil, Product of languages with counter, to appear inTheoret. Comput. Science."},{"key":"CR48","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Separating the polynomial-time hierarchy by oracles,Proc. 26th IEEE Ann. Symp. Foundations of Computer Science, 1985, 1?10.","DOI":"10.1109\/SFCS.1985.49"},{"key":"CR49","doi-asserted-by":"crossref","unstructured":"A. C. Yao, On ACC and threshold circuits,Proc. 31st IEEE Ann. Symp. Foundations of Computer Science, 1990, 619?627.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01212963.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01212963\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01212963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T22:21:57Z","timestamp":1734992517000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01212963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,12]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1991,12]]}},"alternative-id":["BF01212963"],"URL":"https:\/\/doi.org\/10.1007\/bf01212963","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[1991,12]]}}}