滔滔不绝地说
发表于 2025-3-23 12:54:19
Probability one separation of the Boolean hierarchy,cussed in and ..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 and the method of Bennet and Gill to handle t
RAGE
发表于 2025-3-23 15:16:25
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
发表于 2025-3-23 20:36:50
http://reply.papertrans.cn/87/8604/860334/860334_13.png
GAVEL
发表于 2025-3-24 00:02:06
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
发表于 2025-3-24 05:19:29
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
发表于 2025-3-24 07:50:57
http://reply.papertrans.cn/87/8604/860334/860334_16.png
OTTER
发表于 2025-3-24 12:08:40
http://reply.papertrans.cn/87/8604/860334/860334_17.png
有法律效应
发表于 2025-3-24 15:31:50
http://reply.papertrans.cn/87/8604/860334/860334_18.png
CHASM
发表于 2025-3-24 22:53:38
http://reply.papertrans.cn/87/8604/860334/860334_19.png
不可磨灭
发表于 2025-3-24 23:33:22
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.