Titlebook: STACS 87; 4th Annual Symposium Franz J. Brandenburg,Guy Vidal-Naquet,Martin Wirsi Conference proceedings 1987 Springer-Verlag Berlin Heidel

滔滔不绝地说

Probability one separation of the Boolean hierarchy,cussed in [CH86] and [Wag85]..In this paper, we show that a random oracle . separates the Boolean hierarchy into an infinite hierarchy, i.e. . with probability one..The proof technique is a combination of the “sawing” argument introduced in [CH86] and the method of Bennet and Gill [BG81] to handle t

RAGE

Reversal complexity of multicounter and multihead machines,sals is not closed under complementation..The best known lower bound Ω(n./log.n) on the complexity measure REVERSALS·SPACE·PARALLELISM of multihead alternating machines is improved to Ω(n./log.n). Several strongest lower bounds for different complexity measures are direct consequences of this result

Incisor

GAVEL

On the k-freeness of morphisms on free monoids,phism h: X* → Y* is called k-free if the word h(w) is k-free for every k-free word w in X*. We investigate the general structure of k-free morphisms and give outlines for the proof of the following result: if a non-trivial morphism h: X* → Y*, where card(X)≧2 and card(Y)≧2, is k-free for some intege

Spongy-Bone

Avoidable patterns on 2 letters, is avoidable on an alphabet with two letter. The proof is based essentially on two facts: First, each pattern containing an overlapping factor is avoidable by the infinite word of Thue-Morse; secondly, each pattern without overlapping factor is avoidable by the infinite word of Fibonacci.

EXALT

OTTER

有法律效应

CHASM

不可磨灭

Specification and implementation of concurrently accessed data structures: An abstract data type aphod for this..One direction of future research, is to investigate the introduction of more sophisticated primitives for the construction of non-atomic processes (conditionals, guarded choice,...). Several new questions then arise; in particular, our notion of . implementation should be refined, and our proof methods extended accordingly.