An algebraic approach to data languages and timed languages |
| |
Authors: | Patricia Bouyer Antoine Petit Denis Thrien |
| |
Affiliation: | a LSV, CNRS UMR 8643 & ENS de Cachan, 61, avenue du Président Wilson, 94235, Cachan Cedex, France;b School of Computer Science, McGill University, 3480 University, Montréal, Que., Canada H3A 2A7 |
| |
Abstract: | 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. Our class of recognizable languages properly includes many families of deterministic timed languages that have been proposed until now, and the same holds for non-deterministic versions. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|