Logical Definability on Infinite Traces

Werner Ebinger and Anca Muscholl

Abstract:

The main results of this paper are the equivalence of monadic
second-order logic and recognizability for real trace languages, and
that first-order definable, star-free, and aperiodic real trace
languages form the same class of languages. This generalizes results
on infinite words and on finite traces to infinite traces.

Keywords: Logic in Computer Science, Automata and Formal Languages,
Theory of Parallel and Distributed Computation, Theory of Mazurkiewicz
Traces, Infinite Computation.

@Article{em96,
  author =       "Ebinger, Werner and Muscholl, Anca",
  title =        "Logical definability on infinite traces",
  journal =      TCS,
  pages =        "67-84",
  volume =        "154",
  year =          "1996",
  annote =       "The equivalence of monadic second order definability and
                  recognizability and the equivalence of first order
                  definability, star-freeness, and aperiodicity
                  are generalized to languages of infinite traces.",
  note =         "A preliminary version appeared in "#Pot #
                  "20th " # ICALP # " (ICALP'93), Lund (Sweden) 1993, "
                  # LNCS # " 700, 1993."
}