We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction...
This paper describes a modification of the for the transformation of self-verifying
nondeterministic finite automata to deterministic ones. Using a set
counting argument, the upper bound for this transformation can be
lowered from to
We show that the size of a automaton
and the size of a complete, minimal
automaton accepting a regular
language are polynomially related. More precisely, we show
that if a regular language is accepted by a
Las Vegas automaton having states such that
the probability for a definite answer to occur is at least ,
then , where is the number of the states
of the minimal deterministic automaton accepting .
Earlier this result has been obtained
in [2] by using a reduction to , but here we give a direct...
This paper deals with lower bounds on the approximability of different subproblems of the Traveling
Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general
(unless ). First of all, we present an improved lower bound for the Traveling Salesman Problem
with Triangle Inequality, -TSP for short. Moreover our technique, an extension of the method of
Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality,
respectively,...
Download Results (CSV)