Name
Abstract | ||
|---|---|---|
In this paper we relate two generalisations of the finite monoid recognisers of automata theory for the study of circuit complexity classes: Boolean spaces with internal monoids and typed monoids. Using the setting of stamps, this allows us to generalise a number of results from algebraic automata theory as it relates to Buchiu0027s logic on words. We obtain an Eilenberg theorem, a substitution principle based on Stone duality, a block product principle for typed stamps and, as our main result, a topological semidirect product construction, which corresponds to the application of a general form of quantification. These results provide tools for the study of language classes given by logic fragments such as the Boolean circuit complexity classes. |
Year | Venue | Field |
|---|---|---|
2017 | CSL | Complexity class,Semidirect product,Combinatorics,Automata theory,Boolean circuit,Algebraic number,Circuit complexity,Monoid,Stone duality,Mathematics |
DocType | Citations | PageRank |
Conference | 1 | 0.40 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Célia Borlido | 1 | 1 | 0.40 |
| Silke Czarnetzki | 2 | 1 | 0.40 |
| Mai Gehrke | 3 | 349 | 49.19 |
| Andreas Krebs | 4 | 21 | 8.20 |