Logic and branching automata
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)