Currently displaying 1 – 6 of 6

Showing per page

Order by Relevance | Title | Year of publication

Lower bounds for Las Vegas automata by information theory

Mika HirvensaloSebastian Seibert — 2003

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 L is accepted by a Las Vegas automaton having r states such that the probability for a definite answer to occur is at least p , then r n p , where n is the number of the states of the minimal deterministic automaton accepting L . Earlier this result has been obtained in [2] by using a reduction...

Lower Bounds for Las Vegas Automata by Information Theory

Mika HirvensaloSebastian Seibert — 2010

RAIRO - Theoretical Informatics and Applications

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

Improved Lower Bounds on the Approximability of the Traveling Salesman Problem

Hans-Joachim BöckenhauerSebastian Seibert — 2010

RAIRO - Theoretical Informatics and Applications

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

Page 1

Download Results (CSV)