ω♯-Algebras

Abstract

This article explores a generalization of the algebraic theory of formal languages. Having, as starting point, the work of T. Colcombet on cost functions and stabilization monoids, and of Daviaud et al. on stabilization algebras, this class of algebras is extended to ω♯-algebras and ω♯-automata are also introduced. The equality problem for order ideals (of free ω♯-algebras) recognized by finite ω♯-algebras is answered positively in this context. Various results on formal languages and monoids are generalized to this setting of order ideals and ω♯-algebras. The class of cost functions is proved to be embeddable in the class of recognizable order ideals.

Keywords:

• Automaton
• cost function
• order ideal
• pseudovariety
• regular language
• stabilization algebra

2020 MATHEMATICS SUBJECT CLASSIFICATION:

• 08B20
• 20M07
• 20M35
• 68Q70
• 68Q99

Acknowledgements

The authors would like to thank J.-É. Pin and T. Colcombet for introducing them to the study of stabilisation monoids and cost functions, as well as M. J. J. Branco and A. Malheiro for the pertinent discussions and suggestions. The authors also thank the anonymous referee for his/her comments and the careful reading.

Additional information

Funding

This work was developed within the activities of Centro de Matemática Computacional e Estocástica, CEMAT, and Departamento de Matemática da Faculdade de Ciências da Universidade de Lisboa. It was partially supported by Fundação para a Ciência e a Tecnologia under the projects UIDB/04621/2020, UIDP/04621/2020, UID/MULTI/04621/2019 and PTDC/MAT-PUR/31174/2017, and it counted also with the support of Fundação Calouste Gulbenkian, under the project Estímulo à Investigação 2015.