The Schützenberger product for syntactic spaces

DOI10.4230/LIPICS.ICALP.2016.112zbMATH Open1388.68193arXiv1603.08264OpenAlexW2963106448MaRDI QIDQ4598253FDOQ4598253

Authors: Mai Gehrke, Daniela Petrişan, Luca Reggio 

Publication date: 19 December 2017

Abstract: Starting from Boolean algebras of languages closed under quotients and using duality theoretic insights, we derive the notion of Boolean spaces with internal monoids as recognisers for arbitrary formal languages of finite words over finite alphabets. This leads to a setting that is well-suited for applying existing tools from Stone duality as applied in semantics. The main focus of the paper is the development of topo-algebraic constructions pertinent to the treatment of languages given by logic formulas. In particular, using the standard semantic view of quantification as projection, we derive a notion of Sch"utzenberger product for Boolean spaces with internal monoids. This makes heavy use of the Vietoris construction, and its dual functor, which is central to the coalgebraic treatment of classical modal logic. We show that the unary Sch"utzenberger product for spaces, when applied to a recogniser for the language associated to a formula with a free first-order variable, yields a recogniser for the language of all models of the corresponding existentially quantified formula. Further, we generalise global and local versions of the theorems of Sch"utzenberger and Reutenauer characterising the languages recognised by the binary Sch"utzenberger product. Finally, we provide an equational characterisation of Boolean algebras obtained by local Sch"utzenberger product with the one element space based on an Egli-Milner type condition on generalised factorisations of ultrafilters on words.

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

Recommendations

• Schützenberger products in a category
• A topological approach to recognition
• Quantifiers on languages and codensity monads
• Quantifiers on languages and codensity monads
• On Schützenberger Products of Semirings

zbMATH Keywords

Stone dualitylogic on wordsStone-Čech compactificationalgebraic language theory beyond the regular settingVietoris hyperspace construction

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Stone spaces (Boolean spaces) and related structures (06E15)

Cited In (9)

• Quantifiers on languages and codensity monads
• Title not available (Why is that?)
• Monadic monadic second order logic
• Substitution Principle and semidirect products
• Pro-aperiodic monoids via saturated models
• Whither semantics?
• Codensity, profiniteness and algebras of semiring-valued measures
• Title not available (Why is that?)
• Schützenberger products in a category

This page was built for publication: The Schützenberger product for syntactic spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598253)