Substitution Principle and semidirect products

DOI10.1017/S0960129523000294arXiv2106.12525MaRDI QIDQ6190406

Célia Borlido, Mai Gehrke

Publication date: 5 March 2024

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2106.12525

zbMATH Keywords

semidirect productquantifierformal languagesubstitutionlogic on wordsBoolean space with an internal monoid

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular languages and Stone duality
• Regular languages in \(NC\)
• Closure of varieties of languages under products with counter
• Free profinite semigroups over semidirect products
• Codensity, profiniteness and algebras of semiring-valued measures
• Polyadic spaces and profinite monoids
• Nonuniform ACC Circuit Lower Bounds
• Parity, circuits, and the polynomial-time hierarchy
• Duality and Equational Theory of Regular Languages
• A Topological Approach to Recognition
• The Sch\"utzenberger product for syntactic spaces
• Quantifiers on languages and codensity monads
• Stone Duality and the Substitution Principle
• Logic Meets Algebra: the Case of Regular Languages
• STACS 2005
• Extensions of Topological Spaces
• Stone duality, topological algebra, and recognition.

This page was built for publication: Substitution Principle and semidirect products