Loading [MathJax]/extensions/MathZoom.js
The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed ω-semigroups of width 2 and height ωω. This paper completes the description of this algebraic hierarchy.
We first give a purely algebraic decidability procedure of this partial ordering by introducing a graph representation of finite pointed ω-semigroups allowing to compute their precise Wagner degrees.
The Wagner degree of any ω-rational language can therefore be computed...
The algebraic study of formal languages shows that ω-rational sets correspond precisely to the ω-languages recognizable by finite ω-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the ω-rational language to the ω-semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on...
We investigate automatic presentations of ω-words.
Starting points of our study are the works of Rigo and Maes,
Caucal, and Carton and Thomas concerning lexicographic presentation,
MSO-interpretability in algebraic trees, and the decidability of
the MSO theory of morphic words.
Refining their techniques we observe that the lexicographic
presentation of a (morphic) word is in a certain sense canonical.
We then generalize our techniques to a hierarchy of classes of ω-words
enjoying the above...
This note is about functions ƒ : Aω → Bω
whose graph
is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions
and it is decidable whether such function are continuous or not.
In 1920 W. Sierpinski showed that a function is Baire class 1 if and only if both the
overgraph and the undergraph of f are Fσ. We show that
such characterization is also true for functions on infinite words
if we replace the real...
New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and the last...
New compact representations of infinite graphs are
investigated. Finite automata are used to represent labelled hyper-graphs
which can be also multi-graphs. Our approach consists of a general
framework where vertices are represented by a regular prefix-free language and
edges are represented by a regular language and a function over tuples.
We consider three different functions over tuples:
given a tuple
the first function returns its
first difference, the second one returns its suffix and...
We give a new proof showing that it is not possible to define in monadic second-order logic (MSO) a choice function on the infinite binary tree. This result was first obtained by Gurevich and Shelah using set theoretical arguments. Our proof is much simpler and only uses basic tools from automata theory. We show how the result can be used to prove the inherent ambiguity of languages of infinite trees. In a second part we strengthen the result of the non-existence of an MSO-definable well-founded...
We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog.
Succinctness...
We study the succinctness of monadic second-order logic and a variety
of monadic fixed point logics on trees. All these languages are known to have
the same expressive power on trees, but some can express the same
queries much more succinctly than others. For example, we show that, under
some complexity theoretic assumption, monadic second-order logic is
non-elementarily more succinct than monadic least fixed point logic,
which in turn is non-elementarily more succinct than monadic datalog.
Succinctness...
Currently displaying 1 –
20 of
95