Relationship between Alternating omega-Automata and Symbolically Represented Nondeterministic omega-Automata

  • There is a well known relationship between alternating automata on finite words and symbolically represented nondeterministic automata on finite words. This relationship is of practical relevance because it allows to combine the advantages of alternating and symbolically represented nondeterministic automata on finite words. However, for infinite words the situation is unclear. Therefore, this work investigates the relationship between alternating omega-automata and symbolically represented nondeterministic omega-automata. Thereby, we identify classes of alternating omega-automata that are as expressive as safety, liveness and deterministic prefix automata, respectively. Moreover, some very simple symbolic nondeterminisation procedures are developed for the classes corresponding to safety and liveness properties.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Thomas Tuerk, Klaus Schneider
URN (permanent link):urn:nbn:de:hbz:386-kluedo-13975
Serie (Series number):Interner Bericht des Fachbereich Informatik (340)
Document Type:Report
Language of publication:English
Year of Completion:2005
Year of Publication:2005
Publishing Institute:Technische Universität Kaiserslautern
Faculties / Organisational entities:Fachbereich Informatik
CCS-Classification (computer science):F.1.2 Modes of Computation
DDC-Cassification:004 Datenverarbeitung; Informatik

$Rev: 12793 $