An Algebraic Approach to Data Languages
and Timed Languages
Patricia Bouyer, LSV
Algebra offers an elegant and powerful approach to understand regular languages
and finite automata. Such framework has been notoriously lacking for timed
languages and timed automata. We introduce the notion of monoid recognizability
for data languages, which includes timed languages as special case, in a
way that respects the spirit of the classical situation. We study closure
properties and hierarchies in this model, and prove that emptiness is decidable
under natural hypotheses.