Titlebook: STACS 97; 14th Annual Symposiu Rüdiger Reischuk,Michel Morvan Conference proceedings 1997 Springer-Verlag Berlin Heidelberg 1997 Automat.al

BLA

Semi-dynamic shortest paths and breadth-first search in digraphs,or a sequence of edge insertions, in .) amortized time per operation using linear space. Distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path. These results are extended to the case of integer edge weights i

高歌

Hemiplegia

,Translating regular expressions into small ε-free nondeterministic finite automata,in polynomial time. The best previous conversions result in NFAs of worst case size ..). Moreover, the nonexistence of any linear conversion is proved: we give a language .. described by a regular expression of size .(.) such that every NFA accepting .. is of size . log .).

亵渎

CBC471

Fast online multiplication of real numbers,nteger multiplication which is defined by .(. log(.) log log(.), and . refers to the output precision (1/2).. Our computational model is based on Type-2-machines: The real numbers are given by infinite sequences of symbols which approximate the reals with increasing precision. While reading more and

MAL

The operators min and max on the polynomial hierarchy,s and show that there are other interesting optimization classes beside OptP. We investigate the behavior of these operators on the polynomial hierarchy, in particular we study the inclusion structure of the classes max · P, max · NP, max · coNP, min · P, min · NP and min · coNP. Furthermore we prov

Recessive

Resource-bounded kolmogorov complexity revisited,a . complexity, a new nondeterministic variant of . complexity..We show several results relating time-bounded . and . complexity and their applications to a variety of questions in computational complexity theory including:

glacial

Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-mparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. An at most polynomial gap has been established for the combinational complexity of circuits and for the communication complexity of two-party protocols. We investigate the power of Las Vegas c

dissolution

放肆的你