Deterministic Timed AFA: A New Class of Timed Alternating Finite Automata
- 1 ,
Copyright: © 2020 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.
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.
- 1,348 Views
- 1,471 Downloads
- 0 Citations
- formal languages
- timed automata
- timed alternating finite automata