Apr. 25, 2018

For other publications, including those in Japanese, click here.

[Pre. 21] Mika Shigemizu, Toshio Suzuki and Koki Usami

"Independent distributions on a multi-branching AND-OR tree of height 2" arXiv:1804.06601[cs.DS] (2018).

([Pre. 20] Coming soon)

[Pre. 18] Toshio Suzuki

"Non-depth-first search against independent distributions on an AND-OR tree" arXiv:1709.07358[cs.DS] (2017).

[19] Toshio Suzuki

"An AND-OR-tree connected to leaves via communication channels". International MultiConference of Engineers and Computer Scientists 2018, Hong Kong, 14--16 March, 2018.

In: Lecture Notes in Engineering and Computer Science: Proceedings of The International MultiConference of Engineers and Computer Scientists 2018, IMECS 2018, 14-16 March, 2018, Hong Kong, pp. 185-189. ISBN978-988-14047-8-7. ISSN 2078-0958.

[Doc. 0] Toshio Suzuki,

"Computational complexity of Boolean formulas with query symbols,"

Institute of mathematics, University of Tsukuba, Tsukuba-city, Ibaraki, Japan (January, 1999).

Abstract, 5 pages: PDF

The body of the dissertation, about 100 pages: PDF

[17] Toshio Suzuki

"Kazuyuki Tanaka's work on AND-OR trees and subsequent developments,"

*Annals of the Japan Association for Philosophy of Science*,
25, pp.79--88 (2017),
DOI: 10.4288/jafpos.25.0_79.
This is a survey paper.

[16] Toshio Suzuki

"A solution to Yamakami's problem on non-uniform context-free languages,"

*IAENG International Journal of Applied Mathematics*, Volume 46 Issue 2, pp.187-193 (2016).

[15] Toshio Suzuki and Yoshinao Niida

"Equilibrium points of an AND-OR tree: Under constraints on probability,"

*Annals of Pure and Applied Logic*,
166,
pp. 1150--1164 (2015),
DOI: 10.1016/j.apal.2015.07.002.

Preprint version: arXiv:1401.8175[cs.AI] (2014).

[13] Masahiro Kumabe and Toshio Suzuki

"Resource-bounded martingales and computable Dowd-type generic sets,"

*Information and Computation*
242, pp. 227--248 (2015),
DOI: 10.1016/j.ic.2015.03.004.

This is the complete version of [13a].

[12] Toshio Suzuki and Ryota Nakamura

"The eigen distribution of an AND-OR tree under directional algorithms,"

*IAENG International Journal of Applied Mathematics*, Volume 42 Issue 2, pp.122-128 (2012). MR2975745 68T20.

This is an extended version of [12a].

[9] Masahiro Kumabe, Toshio Suzuki and Takeshi Yamazaki

"Does truth-table of linear norm reduce the one-query tautologies to a random oracle?,"

*Archive for Mathematical Logic*
47, pp. 159--180 (2008).
MR2410812 (2009k:68074) 68Q15 (03D30 68Q25),
DOI:10.1007/s00153-008-0076-4

[8] Tomoyuki Yamakami, Toshio Suzuki,

"Resource bounded immunity and simplicity,"

*Theoretical Computer Science*
347, pp. 90-129 (2005),
MR 2184831 (2006k:68036) 68Q15 (03D10 03D15 03D20 68Q10).

This is the complete version of the paper [8a].

A preprint version is available at arXiv:cs/0407015v2 [cs.CC] .

[7] Toshio Suzuki,

"Bounded truth table does not reduce the one-query tautologies to a random oracle,"

*Archive for Mathematical Logic*
44, pp. 751--762 (2005).
MR2191468 (2007b:68056) 68Q15 (03D15),
DOI:10.1007/s00153-005-0283-1

[6] Toshio Suzuki,

"Degrees of Dowd-type generic oracles,"

*Information and Computation*
176, pp. 66--87 (2002),
MR 2003f:68045 68Q15 (03D15 68Q25),
DOI:10.1006/inco.2002.3149.

Preprint version: PDF

[5] Toshio Suzuki,

"Forcing complexity: minimum sizes of forcing conditions,"

*Notre Dame Journal of Formal Logic*
42, pp. 117--120 (2001) (printed in 2003, by the delay of publisher),
MR1993395 (2004e:68035) 68Q15 (03D15), DOI:10.1305/ndjfl/1054837938.

There is a typo in the definition of **finitely testable** property. See the following Corrigenda.

**Corrigenda (New version: Apr. 25, 2018)**:
PDF

Preprint version: PDF

[4] Toshio Suzuki,

"Complexity of the r-query tautologies in the presence of a generic oracle,"

*Notre Dame Journal of Formal Logic*
41, pp. 142--151 (2000) (printed in 2002, by the delay of publisher),
MR 2003j:68055 68Q15 (03D15), DOI:10.1305/ndjfl/1038234608.

Preprint version: PDF

[3] Toshio Suzuki,

"Recognizing tautology by a deterministic algorithm whose while-loop's execution time is bounded by forcing,"

*Kobe Journal of Mathematics* 15, pp. 91--102 (1998),
MR 2000k:68073 68Q25 (03B05 03B35 03D15).

Preprint version: PDF

[2] Toshio Suzuki,

"About splitting numbers,"

*Proceedings of the Japan Academy* 74 A, pp. 33--35 (1998),
MR 99m:03107 03E55 (03E05 03E35), DOI:10.3792/pjaa.74.33.

[1] Toshio Suzuki,

"Witnessing numbers of Shelah cardinals,"

*Mathematical Logic Quarterly* 39, pp. 62--66 (1993),
MR 95d:03095 03E55, DOI: 10.1002/malq.19930390109.

[14a] Toshio Suzuki and Yuji Hatakeyama

"Geometrical redundancy of street patterns based on threshold of isoperimetric ratio,"

In: IAENG Transactions on Engineering Sciences: Special Issue of the International MultiConference of Engineers and Computer Scientists 2013 and World Congress on Engineering 2013, CRC Press (Leiden, The Netherlands), 2014, pp.91-100. ISBN971-1-138-00136-7.

This is a revised version of [14] publised in book form.

[14] Toshio Suzuki and Yuji Hatakeyama

"Threshold of isoperimetric ratio based on compressibility via invertible affine transformations"

In: Lecture Notes in Engineering and Computer Science: Proceedings of The World Congress on Engineering 2013, 3-5 July, 2013, London, UK, pp.211-215. ISBN978-988-19251-0-7. ISSN 2078-0958.

[13a] Toshio Suzuki

"Resource-bounded randomness and computable Dowd-type generic sets (abstract)" (A joint work with Masahiro Kumabe)

*The Bulletin of Symbolic Logic* 19, p.281 (2013).

This is an abstract of a talk at 12th Asian Logic Conference, 15-20 December 2011, Wellington, New Zealand.

[12b] Toshio Suzuki and Ryota Nakamura

"Probability distributions on an AND-OR tree under directional algorithms"

IAENG Transactions on Electrical Engineering, Volume 1, pp.70-83 (2013).

This is a revised version of [12a] publised in book form.

[12a] Toshio Suzuki and Ryota Nakamura

"Probability distributions achieving the equilibrium of an AND-OR tree under directional algorithms"

In: Lecture Notes in Engineering and Computer Science: Proceedings of The International MultiConference of Engineers and Computer Scientists 2012, IMECS 2012, 14-16 March, 2012, Hong Kong, pp. 194-199. ISBN978-988-19251-1-4. ISSN 2078-0958.

Awarded "Best paper award of the 2012 IAENG International Conference on Computer Science."

[11] Masahiro Kumabe and Toshio Suzuki"Computable Dowd-type generic oracles"

In: "Proceedings of the 11th Asian Logic Conference", World Scientific (Hackensack, NJ), 2011, pp.128--146. ISBN978-981-4360-53-1.

MR2868510 (2012m:68120) 68Q15 (03D15). This is the complete version of [11a].

[11a] Masahiro Kumabe and Toshio Suzuki

"Computable Dowd-type generic oracles (abstract)"

*The Bulletin of Symbolic Logic* 16, pp.295--296 (2010).

"Weak randomness, genericity and Boolean decision trees"

In: T. Arai et al. eds., "Proceedings of the 10th Asian Logic Conference", World Scientific (Hackensack, NJ), 2010, pp.322--344. ISBN978-981-4293-01-3.

MR2798904 (2012f:03062) 03D15 (03D32 68Q15). This is the complete version of [10a].

[10a] Masahiro Kumabe and Toshio Suzuki

"Weak randomness, genericity and Boolean decision trees (abstract)"

*The Bulletin of Symbolic Logic* 15, pp.259--260 (2009).

[8a] Toshio Suzuki, Tomoyuki Yamakami,

"Resource bounded immunity and simplicity (extended abstract),"

In: J. Levy et al. eds., "Exploring New Frontiers of Theoretical Informatics" (Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (TCS2004)), Kluwer Academic Publishers, 2004, pp.81-95. ISBN 1-4020-8140-5.

To my portal site