Document Open Access Logo

The Schützenberger Product for Syntactic Spaces

Authors Mai Gehrke, Daniela Petrisan, Luca Reggio

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.112.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Mai Gehrke
Daniela Petrisan
Luca Reggio

Cite As Get BibTex

Mai Gehrke, Daniela Petrisan, and Luca Reggio. The Schützenberger Product for Syntactic Spaces. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 112:1-112:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.112

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.

Subject Classification

Keywords
  • Stone duality and Stone-Cech compactification
  • Vietoris hyperspace construction
  • logic on words
  • algebraic language theory beyond the regular setting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Adámek, R. Myers, H. Urbat, and S. Milius. Varieties of languages in a category. In LICS, pages 414-425. IEEE, 2015. Google Scholar
  2. F. Bonchi, M. Bonsangue, H. Hansen, P. Panangaden, J. Rutten, and A. Silva. Algebra-coalgebra duality in Brzozowski’s minimization algorithm. ACM Trans. Comput. Logic, 15(1):3:1-3:29, 2014. Google Scholar
  3. M. Branco and J.-É. Pin. Equations defining the polynomial closure of a lattice of regular languages. In Albers et al, editor, ICALP 2009, volume 5556 of Lecture Notes In Computer Science, pages 115-126. Springer-Verlag, 2009. Google Scholar
  4. S. Czarnetzki and A. Krebs. Using duality in circuit complexity. arXiv, abs/1510.04849, 2015. To appear in LATA 2016. URL: http://arxiv.org/abs/1510.04849.
  5. S. Eilenberg. Automata, languages, and machines. Vol. B. Academic Press, New York-London, 1976. Google Scholar
  6. M. Gehrke. Stone duality, topological algebra, and recognition. J. Pure and Appl. Algebra, 2016. Google Scholar
  7. M. Gehrke, S. Grigorieff, and J.-É. Pin. Duality and equational theory of regular languages. In Automata, languages and programming II, volume 5126 of Lecture Notes in Comput. Sci., pages 246-257. Springer, Berlin, 2008. Google Scholar
  8. M. Gehrke, S. Grigorieff, and J.-É. Pin. A topological approach to recognition. In Automata, languages and programming II, volume 6199 of Lecture Notes in Comput. Sci., pages 151-162. Springer, Berlin, 2010. Google Scholar
  9. M. Gehrke, A. Krebs, and J.-É. Pin. Ultrafilters on words for a fragment of logic. Theoret. Comput. Sci., 610(part A):37-58, 2016. Google Scholar
  10. M. Gehrke, D. Petrişan, and L. Reggio. The Schützenberger product for syntactic spaces. arXiv, abs/1603.08264, 2016. Google Scholar
  11. N. Hindman and D. Strauss. Algebra in the Stone-\v Cech compactification. de Gruyter, 2012. Google Scholar
  12. A. Krebs, K.-J. Lange, and S. Reifferscheid. Characterizing TC⁰ in terms of infinite groups. Theory Comput. Syst., 40(4):303-325, 2007. Google Scholar
  13. K. Kuratowski. Topology. Vol. I. Academic Press, New York-London; Państwowe Wydawnictwo Naukowe, Warsaw, 1966. Google Scholar
  14. R. McNaughton and S. Papert. Counter-free automata. The M.I.T. Press, Cambridge, Mass.-London, 1971. With an appendix by William Henneman, M.I.T. Research Monograph, No. 65. Google Scholar
  15. J.-É. Pin. Arbres et hierarchies de concatenation. In ICALP, volume 154 of Lecture Notes in Computer Science, pages 617-628. Springer, 1983. Google Scholar
  16. J.-É. Pin. Algebraic tools for the concatenation product. Theoretical Computer Science, 292(1):317-342, 2003. Selected Papers in honor of Jean Berstel. Google Scholar
  17. J.-É. Pin and P. Weil. Profinite semigroups, Malcev products, and identities. J. of Algebra, 182(3):604-626, 1996. Google Scholar
  18. C. Reutenauer. Theoretical Computer Science 4th GI Conference: Aachen, chapter Sur les varietes de langages et de monoïdes, pages 260-265. Springer, 1979. Google Scholar
  19. M.-P. Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8(2):190-194, 1965. Google Scholar
  20. M. H. Stone. The theory of representations for Boolean algebras. Trans. Amer. Math. Soc., 40(1):37-111, 1936. Google Scholar
  21. H. Straubing. A generalization of the Schützenberger product of finite monoids. Theoret. Comput. Sci., 13(2):137-150, 1981. Google Scholar
  22. H. Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser, 1994. Google Scholar
  23. B. Tilson. Categories as algebra: an essential ingredient in the theory of monoids. J. Pure Appl. Algebra, 48(1-2):83-198, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact