Dissertation:    "Uber die Erkennbarkeit unendlicher Spuren

                  Anca Muscholl

Abstract:
We investigate the family of recognizable laguages of
real traces from the viewpoint of automata-theoretic
characterizations. The main topics covered by this PhDthesis concern 
a proper generalization of McNaughton's Theorem from
infinite words to infinite traces, yielding the characterization of
recognizability by asynchronous deterministic Muller automata; a
complementation construction for asynchronous cellular B{\"u}chi
automata, based on a direct subset construction for asynchronous
cellular automata; the equivalence of the class of star-free and
aperiodic languages of real traces; the closure problem for diamond
B{\"u}chi respectively Muller automata and its complexity; finally, a
discussion on deterministic languages of real traces related to
characterizations by deterministic B{\"u}chi automata of several
types. 

 
Zusammenfassung:
 Unendliche Spuren stellen einen geeigneten Rahmen f"ur die
  Untersuchung nicht-terminierender nebenl"aufiger Systeme dar. Eine
  besonders wichtige Eigenschaft dabei ist die endliche
  Kontrollierbarkeit (Erkennbarkeit) des Verhaltens der Systeme.

 Unter den verschiedenen
  Charakterisierungen von Erkennbarkeit im Kontext unendlicher Spuren
  fehlte lange Zeit ein geeignetes Akzeptormodell, d.h.\ ein auf
  Automaten mit verteilter Kontrolle basierendes deterministisches
  Modell. 

  Wir beantworten diese wichtige Frage in der vorliegenden Arbeit,
  indem wir die Klasse erkennbarer Sprachen unendlicher Spuren durch
  deterministische asynchrone Muller Automaten charakterisieren. Damit
  verallgemeinern wir das Theorem von McNaughton "uber unendliche
  W"orter auf  unendliche Spuren. Wir definieren deterministische
  Sprachen unendlicher Spuren, und zeigen die "Aquivalenz zwischen
  Erkennbarkeit und dem Booleschen Abschlu"s dieser Sprachklasse.

  Die Komplementierung nicht-deterministischer B"uchi Automaten ist
  bereits im Fall der unendlichen W"orter ein wichtiges Problem mit
  interessanten L"osungen. Wir erweitern die Methode des
  Fortschrittsma"ses von N.~Klarlund auf asyn\-chron-zellul"are
  Automaten. Voraussetzung war, da"s wir eines der offenen Problemen
  im Bereich endlicher Spuren l"osen, indem wir eine
  Potenzautomaten-Konstruktion f"ur asynchron-zellul"are Automaten
  angeben. Diese wird anschlie"send f"ur die Komplementierung
  verwendet, um die Konstruktion m"oglichst effizient durchzuf"uhren.