Nicolas, Bedon - Logic and Branching Automata

lmcs:1603 - Logical Methods in Computer Science, October 15, 2015, Volume 11, Issue 4
Logic and Branching Automata

Authors: Nicolas, Bedon

In this paper we study the logical aspects of branching automata, as defined by Lodaya and Weil. We first prove that the class of languages of finite N-free posets recognized by branching automata is closed under complementation. Then we define a logic, named P-MSO as it is a extension of monadic second-order logic with Presburger arithmetic, and show that it is precisely as expressive as branching automata. As a consequence of the effectiveness of the construction of one formalism from the other, the P-MSO theory of the class of all finite N-free posets is decidable.


Source : oai:arXiv.org:1507.02890
DOI : 10.2168/LMCS-11(4:2)2015
Volume: Volume 11, Issue 4
Published on: October 15, 2015
Submitted on: September 30, 2014
Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 81 times.
This article's PDF has been downloaded 29 times.