2026-07-22T09:18:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7706 2024-03-06T10:40:44Z ddc:004 open_access

Stone Duality and the Substitution Principle Borlido, Célia Czarnetzki, Silke Gehrke, Mai Krebs, Andreas C-variety of languages typed monoid Boolean space with an internal monoid substitution principle semidirect product 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 Büchi's 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Célia Borlido and Silke Czarnetzki and Mai Gehrke and Andreas Krebs 2017 Is Part Of LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2017.13 urn:nbn:de:0030-drops-77060 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.13 eng https://creativecommons.org/licenses/by/3.0/legalcode