Language equations for timed alternating finite automata
Authors:
Abdelaziz Fellah a;
Carma Harding a
| Affiliation: | a Department of Mathematics and Computer Science University of Lethbridge Lethbridge AB Canada T1K 3M4. |
DOI:
10.1080/0020716031000148205
Publication Frequency:
15 issues per year
Published in:
International Journal of Computer Mathematics,
Volume
80,
Issue
9
September
2003
, pages 1075
- 1091
Subjects:
Analysis - Mathematics;
Bioinformatics;
Computer Mathematics;
Discrete Mathematics;
Mathematical Finance;
Mathematical Logic;
Mathematical Numerical Analysis;
Systems & Computer Architecture;
Formats available:
PDF
(English)
View Article:
View Article (PDF)
Abstract
Traditionally, finite state automata are untimed or asynchronous models of computation in which only the ordering of events, not the time at which events occur, would affect the result of a computation. For real-time systems, it is important to augment these models of computation with a notion of time. For this purpose timed automata have become a powerful canonical model for describing timed behaviors and an effective tool for modeling real-time computations. In this paper, we extend the notion of timed alternating finite automata (TAFA), a class of alternating finite automata (AFA) extended with a finite set of real-valued clocks, and we present an algebraic interpretation of TAFA which parallels that of timed regular expressions and language equations. We further extend the equational representation of AFA to describe timed alternating finite automata, and explore solutions for such equations over time languages.
|
| Keywords: Timed Automata; Timed Alternating Finite Automata; Timed Regular Expressions; Language Equations |

Download Citation

CiteULike
Del.icio.us
BibSonomy
Connotea