Name
Abstract | ||
|---|---|---|
We study the regular languages recognized by polynomial-length programs over finite semigroups belonging to product varieties V ∗ LI , where V is a variety of finite monoids, and LI is the variety of finite locally trivial semigroups. In the case where the semigroup variety has a particular closure property with respect to programs, we are able to give precise characterizations of these regular languages. As a corollary we obtain new proofs of the results of Barrington, Compton, Straubing and Therien characterizing the regular languages in certain circuit complexity classes. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0304-3975(96)00297-6 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
finite semigroup variety | Journal | 180 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 4 |
PageRank | References | Authors |
0.42 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pierre Péladeau | 1 | 48 | 5.45 |
| Howard Straubing | 2 | 528 | 60.92 |
| Denis Thérien | 3 | 671 | 55.71 |