Titlebook: STACS 85; 2nd Annual Symposium K. Mehlhorn Conference proceedings 1985 Springer-Verlag Berlin Heidelberg 1985 Factor.NP.Notation.algorithms

forthy

键琴

On the single-operation worst-case time complexity of the disjoint set union problem,n time complexity in the worst-case. Also we define a class of algorithms for the disjoint set union problem, which includes the class of algorithms defined by Tarjan. We prove that any algorithm from this class has at least ω(log n/loglog n) single-operation time complexity in the worst-case.

多产鱼

Anthem

Non-deterministic two-tape automata are more powerful than deterministic ones,grammars. It is shown that, in contrast to the one-tape case, deterministic two-tape automata are less powerful than non-deterministic ones. The counterexample is closely related to a linear context-free language of unbounded degree of ambiguity.

coagulate

Pantry

Insubordinate

,On Lovász’ lattice reduction and the nearest lattice point problem,(. = const.) to a given point in ... We prove that each of two straightforward fast heuristic procedures achieves this goal when applied to a lattice given by a Lovász-reduced basis. The verification of one of them requires proving a geometric feature of Lovász-reduced bases: a .. lower bound on the

needle

Chipmunk

痛苦一生

Non-deterministic two-tape automata are more powerful than deterministic ones,e tape, they can read simultaneously from two tapes. They accept just the rational subsets of X* × Y*, and are closely related to linear context-free grammars. It is shown that, in contrast to the one-tape case, deterministic two-tape automata are less powerful than non-deterministic ones. The count