Research Article Open Access

Deterministic Timed AFA: A New Class of Timed Alternating Finite Automata

Abdelaziz Fellah1, Zachary Friggstad1 and Soufiane Noureddine1
  • 1 ,
Journal of Computer Science
Volume 3 No. 1, 2007, 1-8

DOI: https://doi.org/10.3844/jcssp.2007.1.8

Submitted On: 15 March 2006 Published On: 31 January 2007

How to Cite: Fellah, A., Friggstad, Z. & Noureddine, S. (2007). Deterministic Timed AFA: A New Class of Timed Alternating Finite Automata. Journal of Computer Science, 3(1), 1-8. https://doi.org/10.3844/jcssp.2007.1.8

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.

  • 1,348 Views
  • 1,471 Downloads
  • 0 Citations

Download

Keywords

  • Automata
  • formal languages
  • timed automata
  • timed alternating finite automata