On logical definability of $\omega$-trace languages

Werner Ebinger

Abstract:
Our main result is the equivalence of monadic second order logic and
recognizability for languages of infinite traces.  This is a
generalization of the work of W. Thomas.  We propose a logical
characterization that is independent of any special sort of trace
automata.  For another approach we use standard constructions and
B\"uchi asynchronous cellular automata defined by P. Gastin and
A. Petit.

@inproceedings{ebi92,
   author = "Ebinger, Werner",
   booktitle = "{P}roceedings {ASMICS} {W}orkshop {I}nfinite {T}races, {T}{\"u}ingen",
   editor = "Diekert, Volker and Ebinger, Werner",
   pages = "106-122",
   publisher = "Universit{\"a}t Stuttgart, Fakult{\"a}t Informatik",
   series = "Bericht 4/92",
   title = "On logical definability of $\omega$-trace languages",
   year = "1992",
   annote = ""
}