Logic and branching automata

Copyright informations

The final publication is available at link.springer.com.


The first result presented in this paper is the closure under complementation of the class or languages of finite N-free posets recognized by branching automata. Relying on this, we propose a logic, named Presburger-MSO or P-MSO for short, precisely as expressive as branching automata. The P-MSO theory of the class of all finite N-free posets is decidable.


N-free posets, series-parallel posets, sp-rational languages, automata, commutative monoids, monadic second-order logic, Presburger logic.

ACM 1998 classification

F.1.1 Models of Computation, F.4.1 Mathematical Logic, F.4.3 Formal Languages



PDF file (315 Ko)

Valid HTML 4.01!