{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,29]],"date-time":"2024-01-29T03:38:02Z","timestamp":1706499482422},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1990,12,1]],"date-time":"1990-12-01T00:00:00Z","timestamp":660009600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1990,12]]},"DOI":"10.1007\/bf02090772","type":"journal-article","created":{"date-parts":[[2005,8,15]],"date-time":"2005-08-15T07:01:07Z","timestamp":1124089267000},"page":"147-164","source":"Crossref","is-referenced-by-count":5,"title":["Extensions of an idea of McNaughton"],"prefix":"10.1007","volume":"23","author":[{"given":"David A.","family":"Mix Barrington","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02090772_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, \u2211 1 1 formulae on finite structures,Ann. Pure Appl. Logic 24 (1983), 1\u201348.","journal-title":"Ann. Pure Appl. Logic"},{"key":"BF02090772_CR2","doi-asserted-by":"crossref","unstructured":"E. Allender,P-uniform circuit complexity,J. Assoc. Comput. Mach.,36(4) (Oct. 1989), 912\u2013928. Also Technical Report DCS-TR-198 (Aug. 1986), Department of Computer Science, Rutgers University.","DOI":"10.1145\/76359.76370"},{"issue":"1","key":"BF02090772_CR3","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. A. Barrington","year":"1989","unstructured":"D. A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages inNC 1 ,J. Comput. System Sci. 38 (1) (Feb. 1989), 150\u2013164.","journal-title":"J. Comput. System Sci."},{"key":"BF02090772_CR4","unstructured":"D. A. M. Barrington, K. Compton, H. Straubing, and D. Th\u00e9rien, Regular languages inNC 1, Technical Report BCCS-88-02 (Oct. 1988), Boston College. Revised versionJ. Comput. System Sci., to appear."},{"key":"BF02090772_CR5","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0020-0190(89)90052-5","volume":"32","author":"D. A. M. Barrington","year":"1989","unstructured":"D. A. M. Barrington and J. Corbett, On the relative complexity of some languages inNC 1,Inform Process. Lett. 32 (1989), 251\u2013256.","journal-title":"Inform Process. Lett."},{"key":"BF02090772_CR6","unstructured":"D. A. M. Barrington and J. Corbett, A note on some languages in uniformACC 0,Theoret. Comput. Sci., to appear."},{"key":"BF02090772_CR7","doi-asserted-by":"crossref","unstructured":"D. A. M. Barrington, N. Immerman, and H. Straubing, On uniformity withinNC 1,Structure in Complexity Theory: Third Annual Conference (Washington: IEEE Computer Society Press, 1988), 47\u201359. Revised versionJ. Comput. System Sci., to appear.","DOI":"10.1109\/SCT.1988.5262"},{"issue":"4","key":"BF02090772_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 and D. Th\u00e9rien, Finite monoids and the fine structure ofNC 1,J. Assoc. Comput. Mach. 35 (4) (Oct. 1988), 941\u2013952.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02090772_CR9","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P. W. Beame","year":"1986","unstructured":"P. W. Beame, S. A. Cook, and H. J. Hoover, Log-depth circuits for division and related problems,SIAM J. Comput. 15 (1986), 994\u20131003.","journal-title":"SIAM J. Comput."},{"key":"BF02090772_CR10","doi-asserted-by":"crossref","unstructured":"J. Boyar, G. Frandsen and C. Sturtivant, An algebraic model for bounding circuit threshold depth, Technical Report 88-005 (April 1988), University of Chicago.","DOI":"10.7146\/dpb.v17i239.7595"},{"key":"BF02090772_CR11","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J. R. B\u00fcchi","year":"1960","unstructured":"J. R. B\u00fcchi, Weak second-order arithmetic and finite automata,Z. Math. Logik Grundlag. Math. 6 (1960), 66\u201392.","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"BF02090772_CR12","first-page":"1","volume-title":"On a decision method in restricted second-order arithmetic","author":"J. R. B\u00fcchi","year":"1962","unstructured":"J. R. B\u00fcchi, On a decision method in restricted second-order arithmetic,Proc. 1960 Internat. Congress on Logic, Methodology, and Philosophy of Science (Palo Alto, CA: Stanford University Press, 1962), 1\u201311."},{"key":"BF02090772_CR13","doi-asserted-by":"crossref","unstructured":"S. R. Buss, The Boolean formula value problem is in ALOGTIME,Proc. 19th ACM Symp. on Theory of Computing (1987), 123\u2013131.","DOI":"10.1145\/28395.28409"},{"issue":"2","key":"BF02090772_CR14","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. K. Chandra","year":"1984","unstructured":"A. K. Chandra, L. J. Stockmeyer, and U. Vishkin, Constant depth reducibility,SIAM J. Comput. 13 (2) (1984), 423\u2013439.","journal-title":"SIAM J. Comput."},{"key":"BF02090772_CR15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook, A taxonomy of problems with fast parallel algorithms,Inform. and Control 64 (1985), 2\u201322.","journal-title":"Inform. and Control"},{"issue":"2","key":"BF02090772_CR16","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht, An application of games to the completeness problem for formalized theories,Fund. Math. 49 (2) (1961), 129\u2013141.","journal-title":"Fund. Math."},{"key":"BF02090772_CR17","volume-title":"Automata, Languages, and Machines, Vol. B","author":"S. Eilenberg","year":"1976","unstructured":"S. Eilenberg,Automata, Languages, and Machines, Vol. B (New York: Academic Press, 1976)."},{"key":"BF02090772_CR18","first-page":"43","volume-title":"Generalized First-Order Spectra and Polynomial-Time Recognizable Sets","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets,SIAM-AMS Proceedings, Vol. 7 (Providence, RI: American Mathematical Society, 1974), 43\u201373."},{"issue":"1","key":"BF02090772_CR19","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"R. Fra\u00efss\u00e9, Sur quelques classifications des syst\u00e8mes de relations, Thesis (1953), Universit\u00e9 de Paris. AlsoAlger-Math\u00e9matiques 1 (1) (1954), 35\u2013182.","journal-title":"Alger-Math\u00e9matiques"},{"key":"BF02090772_CR20","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1002\/malq.19560020504","volume":"2","author":"R. Fra\u00efss\u00e9","year":"1956","unstructured":"R. Fra\u00efss\u00e9, Application des \u03b3-operateurs au calcul logique du premier echelon,Z. Math. Logik Grundlag. Math.,2 (1956), 76\u201392.","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"BF02090772_CR21","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. B. Saxe, and M. Sipser, Parity, circuits, and the polynomialtime hierarchy,Math. System Theory 17 (1984), 13\u201327.","journal-title":"Math. System Theory"},{"key":"BF02090772_CR22","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0019-9958(84)80062-5","volume":"61","author":"Y. Gurevich","year":"1984","unstructured":"Y. Gurevich and H. R. Lewis, A logic for constant depth circuits,Inform. and Control 61 (1984), 65\u201374.","journal-title":"Inform. and Control"},{"key":"BF02090772_CR23","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation (Reading, Ma: Addison-Wesley, 1979)."},{"key":"BF02090772_CR24","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman, Relational queries computable in polynomial time,Inform. and Control 68 (1986), 86\u2013104.","journal-title":"Inform. and Control"},{"issue":"4","key":"BF02090772_CR25","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, Languages that capture complexity classes,SIAM J. Comput. 16 (4) (1987), 760\u2013778.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"BF02090772_CR26","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman, Nondeterministic space is closed under complementation,SIAM J. Comput. 17 (5) (1988), 935\u2013938.","journal-title":"SIAM J. Comput."},{"key":"BF02090772_CR27","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"N. Immerman, Expressibility and parallel complexity,SIAM J. Comput. 18 (1989), 625\u2013638.","journal-title":"SIAM J. Comput."},{"key":"BF02090772_CR28","volume-title":"The Algebraic Theory of Machines, Languages, and Semigroups","author":"K. B. Krohn","year":"1968","unstructured":"K. B. Krohn, J. Rhodes, and B. Tilson, in M. A. Arbib, ed.,The Algebraic Theory of Machines, Languages, and Semigroups (New York: Academic Press, 1968)."},{"key":"BF02090772_CR29","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0019-9958(77)90443-0","volume":"33","author":"R. E. Ladner","year":"1977","unstructured":"R. E. Ladner, Application of model-theoretic games to discrete linear orders and finite automata,Inform. and Control 33 (1977), 281\u2013303.","journal-title":"Inform. and Control"},{"key":"BF02090772_CR30","volume-title":"Semigroups and Combinatorial Applications","author":"G. Lallement","year":"1979","unstructured":"G. Lallement,Semigroups and Combinatorial Applications (New York: Wiley, 1979)."},{"key":"BF02090772_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/BFb0035785","volume-title":"Automata theory meets circuit complexity","author":"P. McKenzie","year":"1989","unstructured":"P. McKenzie and D. Th\u00e9rien, Automata theory meets circuit complexity,Proc. 16th ICALP Lecture Notes in Computer Science, Vol. 372 (Berlin: Springer-Verlag, 1989), 589\u2013602."},{"key":"BF02090772_CR32","unstructured":"R. McNaughton, Symbolic logic and automata, Technical Note 60\u2013244 (July 1960), Wright Air Development Division, Wright-Patterson AFB, Ohio."},{"key":"BF02090772_CR33","unstructured":"R. McNaughton, B\u00fcchi's sequential calculus, Technical Report 89-8 (1989), Department of Computer Science, Rensselaer Polytechnic Institute."},{"key":"BF02090772_CR34","unstructured":"R. McNaughton, personal communication (1989)."},{"key":"BF02090772_CR35","volume-title":"Counter-Free Automata","author":"R. McNaughton","year":"1971","unstructured":"R. McNaughton and S. Papert,Counter-Free Automata (Cambridge, MA: MIT Press, 1971)."},{"key":"BF02090772_CR36","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1145\/321510.321513","volume":"16","author":"A. R. Meyer","year":"1969","unstructured":"A. R. Meyer, A note on star-free events,J. Assoc. Comput. Mach. 16 (1969), 220\u2013225.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02090772_CR37","unstructured":"B. Molzan, Expressibility and nonuniform complexity classes, preprint (1988), Akademie der Wissenschaften der DDR."},{"issue":"3","key":"BF02090772_CR38","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 and G. Schnitger, Parallel computation with threshold functions,J. Comput. System Sci. 36 (3) (1988), 278\u2013302.","journal-title":"J. Comput. System Sci."},{"key":"BF02090772_CR39","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/0022-0000(86)90037-1","volume":"32","author":"D. Perrin","year":"1986","unstructured":"D. Perrin and J. E. Pin, First-order logic and star-free sets,J. Comput. System Sci. 32 (1986), 393\u2013406.","journal-title":"J. Comput. System Sci."},{"key":"BF02090772_CR40","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of Formal Languages","author":"J. E. Pin","year":"1986","unstructured":"J. E. Pin,Varieties of Formal Languages (New York: Plenum, 1986)."},{"key":"BF02090772_CR41","doi-asserted-by":"crossref","unstructured":"N. Pippenger, On simultaneous resource bounds (preliminary version),Proc. 20th IEEE Symp. on Foundations of Computer Science (1979), 307\u2013311.","DOI":"10.1109\/SFCS.1979.29"},{"issue":"4","key":"BF02090772_CR42","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},Mat. Zametki 41 (4) (April 1987), 598\u2013607 (in Russian). English translationMath. Notes 41 (4) (Sept. 1987), 333\u2013338.","journal-title":"Mat. Zametki"},{"key":"BF02090772_CR43","doi-asserted-by":"crossref","unstructured":"J. H. Reif, On threshold circuits and polynomial computation,Second Structure in Complexity Theory Conference (1987), 118\u2013123.","DOI":"10.1109\/PSCT.1987.10319260"},{"key":"BF02090772_CR44","volume-title":"Opportunities and Constraints of Parallel Computing","year":"1989","unstructured":"J. L. C. Sanz, editor,Opportunities and Constraints of Parallel Computing (New York: Springer-Verlag, 1989)."},{"key":"BF02090772_CR45","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\u2013194.","journal-title":"Inform. and Control"},{"key":"BF02090772_CR46","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity,Proc. 19th ACM STOC Symp. (1987), 77\u201382.","DOI":"10.1145\/28395.28404"},{"issue":"1","key":"BF02090772_CR47","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1976","unstructured":"L. J. Stockmeyer, The polynomial time hierarchy,Theoret. Comput. Sci. 3 (1) (1976), 1\u201322.","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"BF02090772_CR48","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"L. Stockmeyer and U. Vishkin, Simulation of parallel random access machines by circuits,SIAM J. Comput. 13 (2) (1984), 409\u2013422.","journal-title":"SIAM J. Comput."},{"key":"BF02090772_CR49","doi-asserted-by":"crossref","unstructured":"H. Straubing, D. Th\u00e9rien, and W. Thomas, Regular languages defined with generalized quantifiers,Proc. 15th ICALP (1988), 561\u2013575.","DOI":"10.1007\/3-540-19488-6_142"},{"key":"BF02090772_CR50","first-page":"96","volume":"33","author":"R. Szelepsc\u00e9nyi","year":"1987","unstructured":"R. Szelepsc\u00e9nyi, The method of forcing for nondeterministic automata,Bull. European Assoc. Theoret. Comput. Sci. 33 (Oct. 1987), 96\u201399.","journal-title":"Bull. European Assoc. Theoret. Comput. Sci."},{"key":"BF02090772_CR51","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/0022-0000(82)90016-2","volume":"25","author":"W. Thomas","year":"1982","unstructured":"W. Thomas, Classifying regular events in symbolic logic,J. Comput. System Sci. 25 (1982), 360\u2013376.","journal-title":"J. Comput. System Sci."},{"key":"BF02090772_CR52","doi-asserted-by":"crossref","unstructured":"M. Vardi, Complexity of relational query languages,Proc. 14th ACM STOC Symp. (1982), 137\u2013146.","DOI":"10.1145\/800070.802186"},{"key":"BF02090772_CR53","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"I. Wegener,The Complexity of Boolean Functions (New York: Wiley; Stuttgart: Teubner, 1987)."},{"key":"BF02090772_CR54","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Circuits and local computation,Proc. 21st ACM STOC Symp. (1989), 186\u2013196.","DOI":"10.1145\/73007.73025"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02090772.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02090772\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02090772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,29]],"date-time":"2024-01-29T02:42:35Z","timestamp":1706496155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02090772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,12]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,12]]}},"alternative-id":["BF02090772"],"URL":"https:\/\/doi.org\/10.1007\/bf02090772","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,12]]}}}