Generalized Eilenberg Theorem: Varieties of Languages in a Category

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00332930" target="_blank" >RIV/68407700:21230/19:00332930 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1145/3276771" target="_blank" >https://doi.org/10.1145/3276771</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3276771" target="_blank" >10.1145/3276771</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Generalized Eilenberg Theorem: Varieties of Languages in a Category

Popis výsledku v původním jazyce

For finite automata as coalgebras in a category C, we study languages they accept and varieties of such languages. This generalizes Eilenberg's concept of a variety of languages, which corresponds to choosing as C the category of Boolean algebras. Eilenberg established a bijective correspondence between pseudovarieties of monoids and varieties of regular languages. In our generalization, we work with a pair C/D of locally finite varieties of algebras that are predual, i.e., dualize, on the level of finite algebras, and we prove that pseudovarieties D-monoids bijectively correspond to varieties of regular languages in C. As one instance, Eilenberg's result is recovered by choosing D = sets and C = Boolean algebras. Another instance, Pin's result on pseudovarieties of ordered monoids, is covered by taking D = posets and C = distributive lattices. By choosing as C = D the self-predual category of join-semilattices, we obtain Polak's result on pseudovarieties of idempotent semirings. Similarly, using the self-preduality of vector spaces over a finite field K, our result covers that of Reutenauer on pseudovarieties of K-algebras. Several new variants of Eilenberg's theorem arise by taking other predualities, e.g., between the categories of non-unital Boolean rings and of pointed sets. In each of these cases, we also prove a local variant of the bijection, where a fixed alphabet is assumed and one considers local varieties of regular languages over that alphabet in the category C.

Název v anglickém jazyce

Generalized Eilenberg Theorem: Varieties of Languages in a Category

Popis výsledku anglicky

For finite automata as coalgebras in a category C, we study languages they accept and varieties of such languages. This generalizes Eilenberg's concept of a variety of languages, which corresponds to choosing as C the category of Boolean algebras. Eilenberg established a bijective correspondence between pseudovarieties of monoids and varieties of regular languages. In our generalization, we work with a pair C/D of locally finite varieties of algebras that are predual, i.e., dualize, on the level of finite algebras, and we prove that pseudovarieties D-monoids bijectively correspond to varieties of regular languages in C. As one instance, Eilenberg's result is recovered by choosing D = sets and C = Boolean algebras. Another instance, Pin's result on pseudovarieties of ordered monoids, is covered by taking D = posets and C = distributive lattices. By choosing as C = D the self-predual category of join-semilattices, we obtain Polak's result on pseudovarieties of idempotent semirings. Similarly, using the self-preduality of vector spaces over a finite field K, our result covers that of Reutenauer on pseudovarieties of K-algebras. Several new variants of Eilenberg's theorem arise by taking other predualities, e.g., between the categories of non-unital Boolean rings and of pointed sets. In each of these cases, we also prove a local variant of the bijection, where a fixed alphabet is assumed and one considers local varieties of regular languages over that alphabet in the category C.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

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

Název periodika

ACM Transactions on Computational Logic

ISSN

1529-3785

e-ISSN

1557-945X

Svazek periodika

20

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

47

Strana od-do

1-47

Kód UT WoS článku

000457990100003

EID výsledku v databázi Scopus

2-s2.0-85059578831