August 20, 2024

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

[Pre 25] Fuki Ito and Toshio Suzuki

"Separation and collapse of equilibria inequalities on AND–OR trees without shape constraints",

preprint, arXiv:2405.20138 [cs.AI].

[24] Masahiro Kumabe, Kenshi Miyabe (*), and Toshio Suzuki

"Solovay reducibility via Lipschitz functions and signed-digit representation",

To appear in *Computability*. Preprint: available on Meiji University Academic Repository.

DOI: 10.3233/COM-230486

*:corresponding author.

[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

[22] Masahiro Kumabe, Kenshi Miyabe, Yuki Mizusawa (*) and Toshio Suzuki

"Solovay reducibility and continuity"

*Journal of Logic and Analysis*, 12:2, pp.1-22 (2020).

*:corresponding author.

Preprint version: ("Solovay reduction and continuity") arXiv:1903.08625[math.LO] (2019).

[21] Mika Shigemizu, Toshio Suzuki and Koki Usami

"Independent distributions on a multi-branching AND-OR tree of height 2"

*Discrete Applied Mathematics*, vol.285, pp.274-282 (October 2020).

DOI: 10.1016/j.dam.2020.05.007

Preprint version: arXiv:1804.06601[cs.DS] (2018).

[18] Toshio Suzuki

"Non-depth-first search against independent distributions on an AND-OR tree"

*Information Processing Letters*, 139, pp. 13-17 (2018). MR3845596 68Q87, DOI: 10.1016/j.ipl.2018.06.013.

Preprint version: arXiv:1709.07358[cs.DS] (2017).

[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).
MR3706299 68T20 68Q25, 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).
MR3526795 68Q45.

[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).
MR3385105 68T20 03D15 68Q17 68Q87 68T27 91A60, 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).
MR3350998 68Q15, 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),
https://doi.org/10.1016/j.tcs.2005.03.055.

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.

[23] Hiroyuki Imai, Masahiro Kumabe, Kenshi Miyabe, Yuki Mizusawa and Toshio Suzuki

"Rational sequences converging to left-c.e. reals of positive effective Hausdorff dimension"

In: NingNing Peng, Kazuyuki Tanaka, Yue Yang, Guohua Wu and Liang Yu eds.,
*Computability Theory and Foundations of Mathematics
Proceedings of the 9th International Conference on Computability Theory and Foundations of Mathematics
The 9th International Conference on Computability Theory and Foundations of Mathematics, Wuhan, China, 21 – 27 March 2019*, pp.97-121, World Scientific, Singapore (2022).

DOI (of the proceeding book): https://doi.org/10.1142/12917

[20] Toshio Suzuki

"Visualization of set inclusion with gloves"

In: Yuri Sato and Zohreh Shams eds.,
Proceedings of International Workshop on Set Visualization and Reasoning (SetVR 2018)
co-located with 10th International Conference on the Theory and Application of Diagrams (Diagrams 2018)
Edinburgh, United Kingdom, June 18, 2018.
*CEUR Workshop Proceedings* Vol-2116, pp.68-75 (2018).

[19a] Toshio Suzuki

"Communication interruption between a game tree and its leaves"

In: "Transactions on Engineering Technologies", Springer, 2020, pp.182-193. ISBN 978-981-32-9807-1 ISBN 978-981-32-9808-8 (eBook) https://doi.org/10.1007/978-981-32-9808-8

This is an extended version of [19].

[19] Toshio Suzuki

"An AND-OR-tree connected to leaves via communication channels".

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.

Awarded "Certificate of Merit for The 2018 IAENG International Conference on Computer Science."

[14a] Toshio Suzuki and Yuji Hatakeyama

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

In: S-I. Ao et al. eds. "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. https://doi.org/10.1201/b16763

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"

In: S-I. Ao et al. eds. "IAENG Transactions on Electrical Engineering, Volume 1", pp.70-83 (2013). https://doi.org/10.1142/8652

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. https://doi.org/10.1142/8201

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. https://doi.org/10.1142/7576

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. DOI:10.1007/b98989

To my portal site