{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T06:44:45Z","timestamp":1760078685141},"reference-count":20,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2000,8,1]],"date-time":"2000-08-01T00:00:00Z","timestamp":965088000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4733,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,8]]},"DOI":"10.1016\/s0304-3975(99)00278-9","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T10:59:17Z","timestamp":1027594757000},"page":"135-148","source":"Crossref","is-referenced-by-count":13,"title":["Programs over semigroups of dot-depth one"],"prefix":"10.1016","volume":"245","author":[{"given":"Alexis","family":"Maciel","sequence":"first","affiliation":[]},{"given":"Pierre","family":"P\u00e9ladeau","sequence":"additional","affiliation":[]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00278-9_BIB1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","article-title":"\u03a311-formulae on finite structures","volume":"24","author":"Ajtai","year":"1983","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0304-3975(99)00278-9_BIB2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","article-title":"Bounded-width polynomial-size branching programs recognize exactly those languages in NC1","volume":"38","author":"Mix Barrington","year":"1989","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB3","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","article-title":"Regular Languages in NC1","volume":"44","author":"Mix Barrington","year":"1992","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB4","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0890-5401(90)90007-5","article-title":"Non-uniform automata over groups","volume":"89","author":"Mix Barrington","year":"1990","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB5","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","article-title":"Finite Monoids and the Fine Structure of NC1","volume":"35","author":"Barrington","year":"1988","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(99)00278-9_BIB6","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0012-365X(73)80005-6","article-title":"Characterization of locally testable events","volume":"4","author":"Brzozowski","year":"1973","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB7","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/S0097539795282432","article-title":"Circuit bottom fan-in and computational power","volume":"27","author":"Cai","year":"1998","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","article-title":"Parity, circuits and the polynomial time hierarchy","volume":"17","author":"Furst","year":"1984","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(99)00278-9_BIB9","unstructured":"J. H\u00e5stad, Almost optimal lower bounds for small depth circuits, in: Advances in Computing Research, Vol. 5, JAI Press, Greenwich, 1989, pp. 143\u2013170."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB10","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","article-title":"Languages that capture complexity classes","volume":"16","author":"Immerman","year":"1987","journal-title":"SIAM J. on Computing"},{"key":"10.1016\/S0304-3975(99)00278-9_BIB11","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1051\/ita\/1983170403211","article-title":"A semigroup characterization of semigroups of dot-depth one languages","volume":"17","author":"Knast","year":"1983","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB12","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/BF01212963","article-title":"NC1","volume":"1","author":"McKenzie","year":"1991","journal-title":"Comput. Complexity"},{"key":"10.1016\/S0304-3975(99)00278-9_BIB13","unstructured":"P. P\u00e9ladeau, Classes de circuits bool\u00e9ens et vari\u00e9t\u00e9s de mono\u0131\u0308des, Ph.D. Thesis, Universit\u00e9 de Paris VI, 1990."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB14","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0304-3975(96)00297-6","article-title":"Finite semigroup varieties defined by programs","volume":"180","author":"P\u00e9ladeau","year":"1997","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB15","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","article-title":"On finite monoids having only trivial subgroups","volume":"8","author":"Sch\u00fctzenberger","year":"1965","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(99)00278-9_BIB16","doi-asserted-by":"crossref","unstructured":"M. Sipser, Borel sets and circuit complexity, in: Proc. 15th ACM Symp. on Theory of Computing, 1983, pp. 61\u201369.","DOI":"10.1145\/800061.808733"},{"key":"10.1016\/S0304-3975(99)00278-9_BIB17","unstructured":"H. Straubing, Varieties of recognizable sets whose syntactic monoids contain solvable groups, Ph.D. Thesis, University of California, Berkeley, 1978."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB18","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1142\/S0218196791000043","article-title":"Constant-depth periodic circuits Internat","volume":"1","author":"Straubing","year":"1991","journal-title":"J. Algebra Comput."},{"key":"10.1016\/S0304-3975(99)00278-9_BIB19","doi-asserted-by":"crossref","unstructured":"H. Straubing, Finite Automata, Formal Logic and Circuit Complexity, Birkhauser, Basel, 1994.","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"10.1016\/S0304-3975(99)00278-9_BIB20","unstructured":"H. Straubing, Languages defined with modular counting quantifiers (extended abstract), in: 15th Annual Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 1373, Springer, Berlin, 1998, pp. 332\u2013343."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599002789?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599002789?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T10:20:23Z","timestamp":1556792423000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599002789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,8]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,8]]}},"alternative-id":["S0304397599002789"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00278-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2000,8]]}}}