{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T09:17:55Z","timestamp":1648977475012},"reference-count":26,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p> Unlike the wreath product, the block product is not associative at the level of varieties. All decomposition theorems involving block products, such as the bilateral version of Krohn\u2013Rhodes' theorem, have always assumed a right-to-left bracketing of the operands. We consider here the left-to-right bracketing, which is generally weaker. <\/jats:p><jats:p> More precisely, we are interested in characterizing for any pseudovarieties of monoids U, V the smallest pseudovariety W that contains U and such that W \u25a1 V = W. This allows us to obtain new decomposition results for a number of important varieties such as DA, DO and DA * G. <\/jats:p><jats:p> We apply these results to characterize the regular languages definable with generalized first-order sentences using only two variables and to shed new light on recent results on regular languages recognized by bounded-depth circuits with a linear number of wires and regular languages with small communication complexity. <\/jats:p>","DOI":"10.1142\/s0218196710005686","type":"journal-article","created":{"date-parts":[[2010,5,5]],"date-time":"2010-05-05T09:01:05Z","timestamp":1273050065000},"page":"319-341","source":"Crossref","is-referenced-by-count":2,"title":["WEAKLY ITERATED BLOCK PRODUCTS AND APPLICATIONS TO LOGIC AND COMPLEXITY"],"prefix":"10.1142","volume":"20","author":[{"given":"HOWARD","family":"STRAUBING","sequence":"first","affiliation":[{"name":"Computer Science Department, Boston College, Chestnut Hill, Massachusetts, USA"}]},{"given":"PASCAL","family":"TESSON","sequence":"additional","affiliation":[{"name":"D\u00e9partement d'Informatique et de G\u00e9nie Logiciel, Universit\u00e9 Laval, Qu\u00e9bec (QC), Canada"}]},{"given":"DENIS","family":"TH\u00c9RIEN","sequence":"additional","affiliation":[{"name":"School of Computer Science, McGill University, Montreal (QC), Canada"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","series-title":"Series in Algebra","volume-title":"Finite Semigroups and Universal Algebra","volume":"3","author":"Almeida J.","year":"1994"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(96)00083-7"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1137\/0219016"},{"key":"rf8","volume-title":"Automata, Languages and Machines","author":"Eilenberg S.","year":"1976"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2003017"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90055-2"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(67)80007-2"},{"key":"rf16","volume-title":"Counter-Free Automata","author":"McNaughton R.","year":"1971"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_10"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90137-0"},{"key":"rf20","first-page":"185","volume":"4","author":"Sch\u00fctzenberger M. P.","journal-title":"Information and Computation"},{"key":"rf21","first-page":"190","volume":"8","author":"Sch\u00fctzenberger M. P.","journal-title":"Information and Computation"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(98)00126-1"},{"key":"rf24","first-page":"627","volume":"17","author":"Steinberg B.","journal-title":"Int. J. Algebra Compu."},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(73)90007-8"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-002-1035-9"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1067"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196704001979"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1190-2"},{"key":"rf35","first-page":"37","volume":"88","author":"Tesson P.","journal-title":"The Complexity Column, Bull. EATCS"},{"key":"rf36","volume":"3","author":"Tesson P.","journal-title":"Logical Methods Computer Science"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(91)90119-M"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1109-3"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(87)90108-3"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90029-I"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196710005686","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:43:11Z","timestamp":1565199791000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196710005686"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":26,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1142\/S0218196710005686"],"URL":"https:\/\/doi.org\/10.1142\/s0218196710005686","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}