Currently displaying 1 – 4 of 4

Showing per page

Order by Relevance | Title | Year of publication

On Distributive Fixed-Point Expressions

Helmut SeidlDamian Niwiński — 2010

RAIRO - Theoretical Informatics and Applications

For every fixed-point expression of alternation-depth , we construct a new fixed-point expression of alternation-depth 2 and size 𝒪 ( r · | e | ) . Expression is equivalent to whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.

Choice functions and well-orderings over the infinite binary tree

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...

Page 1

Download Results (CSV)