11 citations · 16 across the 6 of their papers we have counts for
7 papers
Separation and Collapse of Equilibria Inequalities on AND-OR Trees without Shape Constraints
Fuki Ito, Toshio Suzuki
Herein, we investigate the zero-error randomized complexity, which is the least cost against the worst input, of AND-OR tree computation by imposing various restrictions on the alg…
Solovay reduction and continuity
Masahiro Kumabe, Kenshi Miyabe, Yuki Mizusawa +1
The objective of this study is a better understanding of the relationships between reduction and continuity. Solovay reduction is a variation of Turing reduction based on the dista…
Independent Distributions on a Multi-Branching AND-OR Tree of Height 2
Mika Shigemizu, Toshio Suzuki, Koki Usami
We investigate an AND-OR tree T and a probability distribution d on the truth assignments to the leaves. Tarsi (1983) showed that if d is an independent and identical distribution…
Non-Depth-First Search against Independent Distributions on an AND-OR Tree
Toshio Suzuki
Suzuki and Niida (Ann. Pure. Appl. Logic, 2015) showed the following results on independent distributions (IDs) on an AND-OR tree, where they took only depth-first algorithms into…
A Solution to Yamakami's Problem on Advised Context-free Languages
Toshio Suzuki
Yamakami [2011, Theoret. Comput. Sci.] studies context-free languages with advice functions. Here, the length of an advice is assumed to be the same as that of an input. Let CFL an…
Equilibrium Points of an AND-OR Tree: under Constraints on Probability
Toshio Suzuki, Yoshinao Niida
We study a probability distribution d on the truth assignments to a uniform binary AND-OR tree. Liu and Tanaka [2007, Inform. Process. Lett.] showed the following: If d achieves th…
Resource Bounded Immunity and Simplicity
Tomoyuki Yamakami, Toshio Suzuki
Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, alm…