Immunity and simplicity for exact counting and other counting classes
Immunity and Simplicity for Exact Counting and Other Counting Classes
Ko [26] and Bruschi [11] independently showed that, in some relativized world, PSPACE (in fact, ⊕P) contains a set that is immune to the polynomial hierarchy (PH). In this paper, we study and settle the question of relativized separations with immunity for PH and the counting classes PP, , and ⊕P in all possible pairwise combinations. Our main result is that there is an oracle A relative to which contains a set that is immune BPP⊕P. In particular, this set is immune to PHA and to ⊕PA. Strengthening...
Immunity and simplicity in relativizations of probabilistic complexity classes
Implementation of directed acyclic word graph
An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DAWG for a text is a minimal automaton that accepts all substrings of a text , so it represents a complete index of the text. While all usual implementations of DAWG needed about 30 times larger storage space than was the size of the text, here we show an implementation that decreases this requirement down to four times the size of the text. The method uses a compression of DAWG elements, i. e. vertices,...
Implementing term rewriting by jungle evaluation
Implicitly Representing Arrangements of Lines or Segments.
Improved Bounds on Weak e-Nets for Convex Sets.
Improved lower bounds on the approximability of the traveling salesman problem
Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
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, Delta-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,...
Improving the classification of complexities.
Imre Simon : an exceptional graduate student
This short note reviews the main contributions of the Ph.D. thesis of Imre Simon. His graduate work had major impact on algebraic theory of automata and thirty years later we are in a good position to appreciate how sensitive he was in selecting good problems, and how clever in solving them!
Imre Simon: an exceptional graduate student
This short note reviews the main contributions of the Ph.D. thesis of Imre Simon. His graduate work had major impact on algebraic theory of automata and thirty years later we are in a good position to appreciate how sensitive he was in selecting good problems, and how clever in solving them!
Incremental DFA minimisation
We present a new incremental algorithm for minimising deterministic finite automata. It runs in quadratic time for any practical application and may be halted at any point, returning a partially minimised automaton. Hence, the algorithm may be applied to a given automaton at the same time as it is processing a string for acceptance. We also include some experimental comparative results.
Indécidabilité de la condition IRS
Indépendance algébrique de certaines séries formelles
Independent and identically distributed pseudo-random samples
INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
Indexed categories for program development
Indexed counter languages
Induction and decision procedures.
Mechanization of inductive reasoning is an exciting research area in artificial intelligence and automated reasoning with many challenges. An overview of our work on mechanizing inductive reasoning based on the cover set method for generating induction schemes from terminating recursive function definitions and using decision procedures is presented. This paper particularly focuses on the recent work on integrating induction into decision procedures without compromising their automation.