Thomas Wilke

DIMACS - SYLA Postdoc

Finite Automata and Monadic Second-Order Logic on Finite Trees and on Timed Words

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

September 6, 1995 at 1:00 PM

Abstract:

In this talk we will discuss two unrelated questions I'm interested in, both of which can be traced back to Buechi's observation that monadic second-order logic is as expressive as Rabin/Scott automata on finite strings: 1) Is it decidable whether a given monadic second-order sentence is equivalent to a first-order sentence on binary trees? 2) How can Buechi's result be extended to timed omega automata as introduced by Alur and Dill? The first question is still open; difficulties and partial results will be presented. Regarding the second question the logic of relative distance will be introduced; this logic is expressively complete for timed omega automata.