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
- J.R. Büchi. Weak second-order arithmetic and finite automata.
Z. Math. Logik Grundlagen Math. 6:66-92 (1960).
- W. Ebinger and A. Muscholl. Logical definability of infinite traces.
Theoretical Computer Science 154:67-84 (1996).
- D. Kuske. Towards a language theory of infinite N-free pomsets. Theoretical
Computer Science. To appear (2002).
- D. Kuske. A further step towards a theory of regular MSC languages.
In: STACS 2002, Lecture Notes in Computer Science vol. 2285, pp. 489-500,
Springer, 2002.
- R.E. Ladner. Application of Model Theoretic Games to Discrete Linear
Orders and Finite Automata. Information and Control 33:281-303 (1977).
- R. McNaughton and S. Papert. Counter-Free Automata. MIT Press, Cambridge,
1971.