Deterministic Timed AFA: A New Class of Timed Alternating Finite Automata
Abstract
Timed Alternating Finite Automata (TAFA), a natural generalization of Timed Finite Automata (TFA), are synchronous and powerful models for real-time computations. They become an effective and expressive model for developing embedded systems with real-time constraint computations which are required in many applications. We introduce Deterministic Timed Alternating Finite Automata (DTAFA), a new class of timed alternating finite automata, extended with a finite set of restricted and mutually exclusive real-valued clocks on events which trigger the state transitions of the automaton. We show how to transform deterministic n-state TFA into log n-state DTAFA and state some language properties between TFA, DTAFA, and deterministic TFA. We then show that, unlike TFA and TAFA, DTAFA are closed under all Boolean operations, including the complementation.
DOI: https://doi.org/10.3844/jcssp.2007.1.8
Copyright: © 2007 Abdelaziz Fellah, Zachary Friggstad and Soufiane Noureddine. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,613 Views
- 2,602 Downloads
- 1 Citations
Download
Keywords
- Automata
- formal languages
- timed automata
- timed alternating finite automata