The search session has expired. Please query the service again.
Displaying 301 –
320 of
518
Using counterexample it has been shown that an algorithm which is minimax optimal and over all minimax optimal algorithms is minimean optimal and has a uniform behaviour need not to be minimean optimal.
We show a connection between a recent conjecture of Shallit and an older conjecture of Rauzy for infinite words on a finite alphabet. More precisely we show that a Rauzy-like conjecture is equivalent to Shallit's. In passing we correct a misprint in Rauzy's conjecture.
In this paper, we study the continuity of rational functions realized by
Büchi finite state transducers. It has been shown by Prieur that it
can be decided whether such a function is continuous. We prove here that
surprisingly, it cannot be decided whether such a function f has
at least one point of continuity and that its continuity set C(f)
cannot be computed. In the case of a synchronous rational function, we show that its
continuity set is rational and that it can be computed. Furthermore...
The repetition threshold is a measure of the extent to which
there need to be consecutive (partial) repetitions of finite
words within infinite words
over alphabets of various sizes. Dejean's Conjecture, which has
been recently proven, provides this threshold for all alphabet
sizes. Motivated by a question of Krieger, we deal here with
the analogous threshold when the infinite word is restricted to be a D0L
word. Our main result is that, asymptotically, this threshold
does not exceed the unrestricted...
This paper deals with the decidability of semigroup freeness. More precisely, the
freeness problem over a semigroup S is defined as: given a finite subset
X ⊆ S, decide whether each element of
S has at most one factorization over X. To date, the
decidabilities of the following two freeness problems have been closely examined. In 1953,
Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the
free monoids....
This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability...
This paper deals with the decidability of semigroup freeness. More precisely, the
freeness problem over a semigroup S is defined as: given a finite subset
X ⊆ S, decide whether each element of
S has at most one factorization over X. To date, the
decidabilities of the following two freeness problems have been closely examined. In 1953,
Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the
free monoids....
We present a uniform and easy-to-use technique for deciding the equivalence
problem for deterministic monadic linear recursive programs. The key idea
is to reduce this problem to the well-known group-theoretic problems by
revealing an algebraic nature of program computations. We show that
the equivalence problem for monadic linear recursive programs over finite
and fixed alphabets of basic functions and logical conditions is decidable
in polynomial time for the semantics based on the free monoids...
Currently displaying 301 –
320 of
518