{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:11:07Z","timestamp":1725459067143},"publisher-location":"Berlin\/Heidelberg","reference-count":26,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354051631X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0013122","type":"book-chapter","created":{"date-parts":[[2006,1,12]],"date-time":"2006-01-12T06:46:19Z","timestamp":1137048379000},"page":"199-233","source":"Crossref","is-referenced-by-count":0,"title":["Finite automata and computational complexity"],"prefix":"10.1007","author":[{"given":"Howard","family":"Straubing","sequence":"first","affiliation":[]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"D. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Proc. 18th ACM STOC (1986), pp. 1\u20135.","DOI":"10.1145\/12130.12131"},{"key":"16_CR2","unstructured":"D. Barrington, K. Compton, H. Straubing, and D. Th\u00e9rien, Regular Languages in NC1, Computer Science Department, Tech. Rep. BCCS-88-02, Boston College (1988)."},{"key":"16_CR3","unstructured":"M. Beaudry, Membership Testing in Transformation Monoids, Doctoral Thesis, School of Computer Science, Tech. Rep. TR-SOCS-88.2, McGill University (1988)."},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"L. Babai, E. Luks and A. Seress, Permutation Groups in NC, Proc. 19th ACM STOC (1987), pp. 409\u2013420.","DOI":"10.1145\/28395.28439"},{"key":"16_CR5","unstructured":"M. Beaudry, P. McKenzie, and D. Th\u00e9rien, Testing Memembership: Beyond Permutation Groups, Proc. STACS, (1989)."},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"D.M. Barrington, H. Straubing, and D. Th\u00e9rien, Non-Uniform Automata over Groups, U. Mass Tech. Report, (1988).","DOI":"10.1007\/3-540-18088-5_13"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"D. Barrington and D. Th\u00e9rien, Finite monoids and the fine structure of NC1, Proc. 19th ACM STOC (1987), pp. 101\u2013109.","DOI":"10.1145\/28395.28407"},{"key":"16_CR8","unstructured":"D. Barrington and D. Th\u00e9rien, Nonuniform automata over groups, Proc. 14th ICALP, Springer Lecture Notes in Comp. Sci. (1987), pp. 163\u2013173."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"A. Chandra, S. Fortune and R. Lipton, Unbounded fan-in circuits and associative functions, Proc. 15th ACM STOC, (1983), pp. 52\u201360.","DOI":"10.1145\/800061.808732"},{"key":"16_CR10","unstructured":"S. Eilenberg, Automata, Languages and Machines Vol. B, Academic Press (1974)."},{"key":"16_CR11","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/BF02573031","volume":"1","author":"C. Fennemore","year":"1970","unstructured":"C. Fennemore, All varieties of bands, Semigroup Forum 1 (1970), pp.172\u2013177.","journal-title":"Semigroup Forum"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Hopcroft and E. Luks, Polynomial time algorithms for permutation groups, Proc. 21st IEEE Symp. on the Foundations for Computer Science (1980), pp. 36\u201341.","DOI":"10.1109\/SFCS.1980.34"},{"key":"16_CR13","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe and M. Sipser, Parity, circuits, and the polynomial time hierarchy, J. Math Systems Theory 17, (1984), pp. 13\u201327.","journal-title":"J. Math Systems Theory"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"J. Hastad, Almost optimal lower bounds for small depth circuits, Proc. 18th ACM STOC, (1986), pp. 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"16_CR15","unstructured":"J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley (1979)."},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"D. Kozen, Lower bounds for natural proof systems, Proc. 18th ACM STOC, (1977), pp. 254\u2013266.","DOI":"10.1109\/SFCS.1977.16"},{"key":"16_CR17","unstructured":"E.M. Luks, Parallel algorithms for permutation groups and grah isomorphism, Proc. 27th IEEE Symp. on the Foundations of Computer Science (1986), pp. 292\u2013303."},{"issue":"1","key":"16_CR18","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"R.E. Ladner, The Circuit value problem is log-space complete for P, SIGACT News 7:1, (1975), pp. 18\u201320.","journal-title":"SIGACT News"},{"key":"16_CR19","unstructured":"E.M. Luks and P.McKenzie, Fast parallel computation with permutation groups, Proc. 26th IEEE Symp. on the Foundations of Computer Science (1986), pp. 505\u2013514."},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"P. McKenzie and S.A. Cook, The parallel complexity of the abelian permutaion group membership problem, Proc. 24th IEEE Symp. on the Foundations of Computer Science, (1983), pp 154\u2013161.","DOI":"10.1109\/SFCS.1983.74"},{"key":"16_CR21","unstructured":"J.-E. Pin, Vari\u00e9t\u00e9s de languages formels, Masson (1984)."},{"key":"16_CR22","unstructured":"A.A. Razborov, Lower Bounds for the size of circuits of bounded depth with basis {&, \u2297}, to appear in Mathematical Notes of the Soviet Academy of Sciences, (in Russian)."},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"M. Sipser, Borel sets and circuit complexity, Proc. 15th ACM STOC, (1983), pp. 61\u201369.","DOI":"10.1145\/800061.808733"},{"key":"16_CR24","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 Control 8, (1965), pp. 190\u2013194.","journal-title":"Information and Control"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for boolean circuit complexity, Proc. 19th ACM STOC, (1987), pp. 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"16_CR26","unstructured":"H. Straubing, Semigroups and Languages of dot-depth 2, Proc. 13th ICALP, Springer Lecture Notes in Comp. Sci., (1986), pp. 416\u2013423."}],"container-title":["Lecture Notes in Computer Science","Formal Properties of Finite Automata and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0013122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T22:31:11Z","timestamp":1586644271000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0013122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354051631X"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0013122","relation":{},"subject":[]}}