6533b824fe1ef96bd128147e
RESEARCH PRODUCT
Formations of Monoids, Congruences, and Formal Languages
Enric Cosme LlópezJan RuttenAdolfo Ballester-bolinchesRamon Esteban-romerosubject
Pure mathematicsGeneral Computer ScienceApplied MathematicsData ScienceCWI Technical Report reportFormationsLlenguatges de programacióAbstract family of languagesCongruence relationlcsh:QA75.5-76.95Formal languagesMathematics::Category TheoryFormal languageComputingMethodologies_DOCUMENTANDTEXTPROCESSINGBijectionAutomata theorylcsh:Electronic computers. Computer scienceÀlgebraEquivalence (formal languages)SemigroupsMATEMATICA APLICADAAlgorithmAutomata theoryMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2015-12-01 | Scientific Annals of Computer Science |