Abstracts for the LGTDS workshop

ICGT Conference , Barcelona, October 2002


Algebraic characterizations of first-order logic on posets

Dietrich Kuske

University of Leicester
Leicester
LE1 7RH
UK
d.kuske@mcs.le.ac.uk
Home page:   http://www.mcs.le.ac.uk/~dkuske

Abstract

Büchi's result on the relation between monadic second order logic and recognizability has attracted much attention which is mirrored, e.g., by the generalizations known in the meantime (that are mentioned in some of the other abstracts). McNaughton and Papert discovered a similar relation between first-order logic and aperiodicity. This has been extended to infinite words (Ladner) and to finite and infinite traces (Ebinger and Muscholl).  I will show that a similar relation holds for (infinite) series-parallel pomsets and (infinite) message-sequence charts. Both proofs rely on the result by Ladner for infinite words, but the reduction methods are quite different.  

References