Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/114473
Title: | Substitution Principle and semidirect products | Authors: | Borlido, Célia Gehrke, Mai |
Issue Date: | 2023 | Project: | European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No.670624 UIDB/00324/2020 |
Serial title, monograph or event: | Mathematical Structures in Computer Science | Volume: | 33 | Issue: | 6 | Abstract: | In the classical theory of regular languages the concept of recognition by profinite monoids is an important tool. Beyond regularity, Boolean spaces with internal monoids (BiMs) were recently proposed as a generalization. On the other hand, fragments of logic defining regular languages can be studied inductively via the so-called “Substitution Principle”. In this paper we make the logical underpinnings of this principle explicit and extend it to arbitrary languages using Stone duality. Subsequently we show how it can be used to obtain topo-algebraic recognizers for classes of languages defined by a wide class of first-order logic fragments. This naturally leads to a notion of semidirect product of BiMs extending the classical such construction for profinite monoids. Our main result is a generalization of Almeida and Weil’s Decomposition Theorem for semidirect products from the profinite setting to that of BiMs. This is a crucial step in a program to extend the profinite methods of regular language theory to the setting of complexity theory. | URI: | https://hdl.handle.net/10316/114473 | ISSN: | 0960-1295 1469-8072 |
DOI: | 10.1017/S0960129523000294 | Rights: | openAccess |
Appears in Collections: | I&D CMUC - Artigos em Revistas Internacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Substitution Principle and semidirect products_arxiv.pdf | 596.84 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.