An algebraic approach to data languages and timed languages

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 cas...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2003-05, Vol.182 (2), p.137-162
Main Authors: Bouyer, Patricia, Petit, Antoine, Thérien, Denis
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Language theory and syntactical analysis
Memory organisation. Data processing
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0890-5401
1090-2651
DOI:10.1016/S0890-5401(03)00038-5