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.


    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
    Funding:
      Source : OpenAIRE Graph
    • Deep Drug Discovery and Deployment; Code: PTDC/CCI-BIO/29266/2017

    3 Documents citing this article

    Consultation statistics

    This page has been seen 1082 times.
    This article's PDF has been downloaded 330 times.