[Up]
Logic and branching automata
Copyright informations
The final publication is available at link.springer.com.
Abstract
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.
Keywords
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
Download
PDF file (315 Ko)
