License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.112
URN: urn:nbn:de:0030-drops-62474
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6247/
Go to the corresponding LIPIcs Volume Portal

Gehrke, Mai ; Petrisan, Daniela ; Reggio, Luca

The Schützenberger Product for Syntactic Spaces

pdf-format:
LIPIcs-ICALP-2016-112.pdf (0.6 MB)

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 recognisers and syntactic spaces in a setting that is well-suited for applying 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ützenberger 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ützenberger product for spaces yields a recogniser for the language of all models of the formula EXISTS x.phi(x), when applied to a recogniser for the language of all models of phi(x). Further, we generalise global and local versions of the theorems of Schützenberger and Reutenauer characterising the languages recognised by the binary Schützenberger product.

Finally, we provide an equational characterisation of Boolean algebras obtained by local Schützenberger product with the one element space based on an Egli-Milner type condition on generalised factorisations of ultrafilters on words.

BibTeX - Entry

@InProceedings{gehrke_et_al:LIPIcs:2016:6247,
  author =	{Mai Gehrke and Daniela Petrisan and Luca Reggio},
  title =	{{The Sch{\"u}tzenberger Product for Syntactic Spaces}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{112:1--112:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6247},
  URN =		{urn:nbn:de:0030-drops-62474},
  doi =		{10.4230/LIPIcs.ICALP.2016.112},
  annote =	{Keywords: Stone duality and Stone-Cech compactification, Vietoris hyperspace construction, logic on words, algebraic language theory beyond the regular setting}
}

Keywords: Stone duality and Stone-Cech compactification, Vietoris hyperspace construction, logic on words, algebraic language theory beyond the regular setting
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI