Name
Abstract | ||
|---|---|---|
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-Rhodes' theorem, have always assumed a right-to-left bracketing of the operands. We consider here the left-to-right bracketing, which is generally weaker.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 square V = W. This allows us to obtain new decomposition results for a number of important varieties such as DA, DO and DA * G.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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1142/S0218196710005686 | INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION |
Keywords | Field | DocType |
Block-product, two-variable logics, computational complexity | Discrete mathematics,Combinatorics,Associative property,Algebra,Communication complexity,Monoid,Regular language,Wreath product,Iterated function,Bracketing,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
20 | 2 | 0218-1967 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Howard Straubing | 1 | 528 | 60.92 |
| Pascal Tesson | 2 | 125 | 12.86 |
| Denis Thérien | 3 | 671 | 55.71 |