Eilenberg theorems for free

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00318582" target="_blank" >RIV/68407700:21230/17:00318582 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.43" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.43</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.43" target="_blank" >10.4230/LIPIcs.MFCS.2017.43</a>

Result language
angličtina
Original language name
Eilenberg theorems for free
Original language description
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 Bojańczyk and of Adámek 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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
ISBN
978-3-95977-046-0
ISSN
1868-8969
e-ISSN
—
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl
Event location
Aalborg
Event date
Aug 21, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)