cs.LO cs.FL
Logic and Rational Languages of Scattered and Countable Series Parallel Posets. Let A be an alphabet and SP diamond(A) denote the class of all countable N free partially ordered sets labeled by A , in which chains are scattered linear orderings and antichains are finite. We characterize the rational languages of SP diamond(A) by means of logic. We define an extension of monadic second order logic by Presburger arithmetic, named P MSO, such that a language L of SP diamond(A) is rational if and only if L is the language of a sentence of P MSO, with effective constructions from one formalism to the other. As a corollary, the P MSO theory of SP diamond(A) is decidable.