## 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.