Generalized Eilenberg Theorem: Varieties of Languages in a Category

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Generalized Eilenberg Theorem: Varieties of Languages in a Category

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2019

Confidentiality

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

Name of the periodical

ACM Transactions on Computational Logic

ISSN

1529-3785

e-ISSN

1557-945X

Volume of the periodical

20

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

47

Pages from-to

1-47

UT code for WoS article

000457990100003

EID of the result in the Scopus database

2-s2.0-85059578831