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.MFCS.2017.43
URN: urn:nbn:de:0030-drops-81032
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8103/
Go to the corresponding LIPIcs Volume Portal

Urbat, Henning ; Adámek, Jiri ; Chen, Liang-Ting ; Milius, Stefan

Eilenberg Theorems for Free

pdf-format:
LIPIcs-MFCS-2017-43.pdf (0.6 MB)

Abstract

Eilenberg-type correspondences, relating varieties of languages (e.g., of finite words, infinite words, or trees) to pseudovarieties of finite algebras, form the backbone of algebraic language theory. We show that they all arise from the same recipe: one models languages and the algebras recognizing them by monads on an algebraic category, and applies a Stone-type duality. Our main
contribution is a variety theorem that covers e.g. Wilke's and Pin's
work on infinity-languages, the variety theorem for cost functions of Daviaud, Kuperberg, and Pin, and unifies the two categorical
approaches of Bojanczyk and of Adamek et al. In addition we derive new results, such as an extension of the local variety theorem of Gehrke, Grigorieff, and Pin from finite to infinite words.

BibTeX - Entry

@InProceedings{urbat_et_al:LIPIcs:2017:8103,
  author =	{Henning Urbat and Jiri Ad{\'a}mek and Liang-Ting Chen and Stefan Milius},
  title =	{{Eilenberg Theorems for Free}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8103},
  URN =		{urn:nbn:de:0030-drops-81032},
  doi =		{10.4230/LIPIcs.MFCS.2017.43},
  annote =	{Keywords: Eilenberg's theorem, variety of languages, pseudovariety, monad,  duality}
}

Keywords: Eilenberg's theorem, variety of languages, pseudovariety, monad, duality
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

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