|
- Journal
Articles:
- [J1] with
Luca
Alberucci: On
Modal µ-Calculus
and Gödel-Löb Logic. Studia Logica: 91, 145-169 (2009)
Abstract:
"We show that the modal µ-calculus over GL collapses to the modal
fragment by showing that the fixpoint formula is reached after two
iterations and answer to a question posed by van Benthem in
[vBe06]. Further, we introduce the modal µ∼-calculus by
allowing fixpoint constructors for any formula where the fixpoint
variable appears guarded but not necessarily positive and show that
this calculus over GL collapses to the modal fragment, too. The latter
result allows us a new proof of the
de Jongh, Sambin Theorem and provides a simple algorithm to construct
the fixpoint formula."
- [J2] with
Luca
Alberucci: The
Modal μ-Calculus Hierarchy on Restricted Classes of Transition
Systems. The Journal of Symbolic Logic:
74(4), 1367-1400 (2009)
Abstract:
"We discuss the strictness of the modal µ-calculus hierarchy over
some restricted classes of transition systems. First, we show
that the hierarchy is strict over reflexive frames. By proving the
finite model
theorem for reflexive systems the same results holds for finite models.
Second, we prove that over transitive systems the hierarchy collapses
to the alternation-free fragment. In order to do this the finite model
theorem
for transitive transition systems is also proved. Further, we verify
that if symmetry is added to transitivity the hierarchy collapses
to the purely modal fragment."
- Papers in
Refereed Conferences:
- [C1] with
Jacques
Duparc: Describing
the Wadge Hierarchy for the Alternation Free Fragment of μ-Calculus
(I): The Levels Below ω_1
in:
Arnold Beckmann, Costas Dimitracopoulos, and Benedikt Löwe (eds.):
Logic and Theory of
Algorithms, Fourth Conference on Computability in
Europe, CiE 2008, Athens, Greece, June 2008, Proceedings.
Springer
LNCS 5028, 2008
Abstract:
"The height of the Wadge Hierarchy
for the Alternation Free Fragment of
µ-calculus is known to be at least ϵ_0 . It was conjectured that
the height is exactly ϵ_0 . We make a first step towards the proof of
this conjecture by showing that there is no ∆^µ_2 definable set in
between the levels ω^ω and ω_1 of the Wadge Hierarchy of Borel
Sets."
- [C2] with
Jacques
Duparc: A
Playful Glance at Hierarchical Questions for Two-Way Alternating
Automata
In: Margaret Archibald, Vasco Brattka, Valentin Goranko, Benedikt
Löwe (eds.): Infinity in Logic
and Computation, Selected Papers of the International Conference
Infinity in Computation and Logic, Cape Town, South Africa, November
2007. Springer LNAI (to appear)
Abstract:
"Two-way alternating automata were introduced by Vardi in order to
study the satisfiability problem for the modal µ-calculus
extended with backwards modalities.
In this paper, we present a very simple proof by way of Wadge
games of the strictness of the hierarchy of Motowski indices of two-way
alternating automata over trees."
- [C3] with
Jacques Duparc and Filip
Murlak: Linear Game Automata -
Decidable Hierarchy Problems for Stripped-Down Alternating Tree
Automata [full
version on HAL]. In: Erich
Graedel, Reinhard Kahle (eds.): CSL
09. Springer LNCS 5771, pp. 225-239
Abstract:
"For deterministic tree automata, classical hierarchies, like
Mostowski-Rabin (or index) hierarchy, Borel hierarchy, or Wadge
hierarchy, are known to be decidable. However, when it comes to
non-deterministic tree automata, none of these hierarchies is
even close to be understood. Here we make a second attempt in paving
the way towards a clear understanding of tree automata. We concentrate
on the class of linear game automata (LGA), and prove within this new
context, that all corresponding hierarchies mentioned
above—Mostowski-Rabin, Borel, and Wadge—are decidable. The class LGA is
obtained by taking linear tree automata with alternation restricted to
the choice of path in the input tree. Despite their simplicity, LGA
recognize sets of arbitrary high Borel rank. The actual richness of LGA
is revealed by the height of their Wadge hierarchy: (ω^ω)^ω"
- [C4] with
J. Cabessa,
J.
Duparc and F. Murlak: The Wadge
Hierarchy of Max-Regular Languages (accepted
at the IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science
December 15-17 2009, IIT Kanpur, India)
Abstract:
"Recently, Mikolaj Bojanczyk introduced a class of max-regular
languages, an extension of regular languages of infinite words
preserving many of its usual properties. This new class can be
seen as a different way of generalizing the notion of regularity from
finite to infinite words. This paper compares regular and
max-regular languages in terms of topological complexity. It is proved
that up to Wadge equivalence the classes coincide. Moreover, when
restricted to $\mathbf{\Delta}^0_2$-languages, the classes
contain virtually the same languages. On the other hand,
separating examples of arbitrary complexity exceeding
$\mathbf{\Delta}^0_2$ are constructed."
- Unpublished
/ Submitted Papers:
- [U1] with
Jacques
Duparc: The
Topological Complexity of Models of the Modal μ-Calculus: On The
Alternation Free Fragment and Beyond (submitted)
Abstract:
"This is the extended journal version of [C1]. In this
paper we define set theoretical operations in terms of µ-formulae.
In particular, we introduce the operation given
by an action of a µ-definable
topological property over a
class of models. When considering definability by alternation free
formulae, we obtain the $\mu$-calculus counterpart of the Wadge
hierarchy for weakly alternating tree automata. It was
conjectured that the height of this hierarchy is exactly
$\varepsilon_{0}$. We prove that the degree of a tree language
definable by an alternation free formula is either below $
\omega^\omega$ or above $\omega_1$.
However, very little is known about the Wadge hierarchy for the full µ-calculus,
the problem being that most of the sets definable by a µ-formula
are even not Borel. We make a first step in this
direction by introducing the Wadge hierarchy extending the one for the
alternating free fragment with an action given by a difference of two
$\Pi^1_1$ complete sets."
|
|
|