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.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Thomas Tuerk, Klaus Schneider
URN (Permalink):urn:nbn:de:hbz:386-kluedo-13975
Schriftenreihe (Bandnummer):Interner Bericht des Fachbereich Informatik (340)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2005
Jahr der Veröffentlichung:2005
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):17.11.2005
Fachbereiche / Organisatorische Einheiten:Fachbereich Informatik
CCS-Klassifikation (Informatik):F. Theory of Computation / F.1 COMPUTATION BY ABSTRACT DEVICES / F.1.2 Modes of Computation
DDC-Sachgruppen:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $