Pierre Simonnet

  1. On Recognizable Tree Languages Beyond the Borel Hierarchy.

    Authors: Olivier Finkel, Pierre Simonnet
    Subjects: Logic
    Abstract

    We investigate the topological complexity of non Borel recognizable tree
    languages with regard to the difference hierarchy of analytic sets. We show
    that, for each integer $n \geq 1$, there is a $D_{\omega^n}({\bf
    \Sigma}^1_1)$-complete tree language L_n accepted by a (non deterministic)
    Muller tree automaton. On the other hand, we prove that a tree language
    accepted by an unambiguous B\"uchi tree automaton must be Borel. Then we
    consider the game tree languages $W_{(i,k)}$, for Mostowski-Rabin indices $(i,
    k)$.

  2. On Recognizable Tree Languages Beyond the Borel Hierarchy.

    Authors: Olivier Finkel, Pierre Simonnet
    Subjects: Logic
    Abstract

    We investigate the topological complexity of non Borel recognizable tree
    languages with regard to the difference hierarchy of analytic sets. We show
    that, for each integer $n \geq 1$, there is a $D_{\omega^n}({\bf
    \Sigma}^1_1)$-complete tree language L_n accepted by a (non deterministic)
    Muller tree automaton. On the other hand, we prove that a tree language
    accepted by an unambiguous B\"uchi tree automaton must be Borel. Then we
    consider the game tree languages $W_{(i,k)}$, for Mostowski-Rabin indices $(i,
    k)$.

Syndicate content