Suchergebnisse

The main goal in this paper is to use a dual equivalence in automata theory started in [25] and developed in [3] to prove a general version of the Eilenberg-type theorem presented in [4]. Our principal results confirm the existence of a bijective correspondence between three concepts; formations of monoids, formations of languages and formations of congruences. The result does not require finiteness on monoids, nor regularity on languages nor finite index conditions on congruences. We relate our work to other results in the field and we include applications to non-r-disjunctive languages, Reiterman s equational description of pseudovarieties and varieties of monoids. ; The authors gratefully acknowledge various discussions with Jean-Eric Pin. This work has been supported by the grants MTM2010-19938-C03-01 from the Ministerio de Ciencia e Innovacion (Spanish Government) and MTM2014-54707-C3-1-P from the Ministerio de Economia y Competitividad (Spanish Government) and FEDER (European Union). The first author has been supported by the grant No. 11271085 from the National Natural Science Foundation of China. The second author has been supported by the predoctoral grant AP2010-2764 from the Ministeriode Educacion (Spanish Government) and by an internship from CWI. ; Ballester Bolinches, A.; Cosme-Llópez, E.; Esteban Romero, R.; Rutten, J. (2015). Formations of monoids, congruences, and formal languages. Scientific Annals of Computer Science. 25(2):171-209. https://doi.org/10.7561/SACS.2015.2.171 ; S ; 171 ; 209 ; 25 ; 2