omega sharp algebras

Communications in Algebra, 49 (9) (2021), 3969–3999
https://doi.org/10.1080/00927872.2021.1910283

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 omega sharp-algebras and omega sharp -automata are also introduced. The equality problem for order ideals (of free omega sharp-algebras) recognized by finite omega sharp -algebras is answered positively in this context. Various results on formal languages and monoids are generalized to this setting of order ideals and omega sharp-algebras. The class of cost functions is proved to be embeddable in the class of recognizable order ideals