Logic and Branching Automata

Bedon Nicolas

doi:10.2168/LMCS-11(4:2)2015

Bedon Nicolas - Logic and Branching Automata

lmcs:1603 - Logical Methods in Computer Science, October 15, 2015, Volume 11, Issue 4 - https://doi.org/10.2168/LMCS-11(4:2)2015

Logic and Branching AutomataArticle

Authors: Bedon Nicolas

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.

https://doi.org/10.2168/LMCS-11(4:2)2015

Source: arXiv.org:1507.02890

Volume: Volume 11, Issue 4

Published on: October 15, 2015

Imported on: September 30, 2014

Keywords: Computer Science - Formal Languages and Automata Theory, Computer Science - Logic in Computer Science

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph