Toshio Suzuki: publications in English

Sep.22, 2017


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

Preprint

[Pre. 18] Toshio Suzuki

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

slideslide,   movievideo (YouTube).


New

[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). This is a survey paper.


Doctoral Dissertation

[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


Refereed Papers in Journals

[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).

Preprint version: "A solution to Yamakami's problem on advised context-free languages," arXiv:1502.00367[cs.FL] (2015).

[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.

Corrigenda: 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.


Refereed Papers in Major International Conferences

[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.

Online version: click here.

[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."

Online version: click here.

[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).

[10] Toshio Suzuki and Masahiro Kumabe

"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