## Basic Information

### Major Professional Backgrounds

- 1995/11/01, 1997/09/30, Kyushu Institute of Design, Faculty of Design, Lecturer
- 1997/10/01, 2001/03/31, Hiroshima University, Faculty of Engineering, Associate Professor
- 2001/04/01, 2007/03/31, Hiroshima University, Graduate School of Engineering, Associate Professor
- 1993/04/01, 1995/03/31, Japan Society for the Promotion of Science, Special Postdoctoral Researcher
- 1995/04/01, 1995/10/31, Kyushu University, Research Associate
- 2007/04/01, 2015/08/31, Hiroshima University, Graduate School of Engineering, Associate Professor
- 2014/09/01, 2020/03/31, Hiroshima University, Graduate School of Engineering, Professor

### Educational Backgrounds

- Kyushu University, Graduate School, Division of Engineering, Department of Computer Science and Communication Engineering, Japan, 1990/04, 1995/03
- Yamaguchi University, Faculty of Engineering, Japan, 1986/04, 1990/03

### Academic Degrees

- Doctor of Engineering, Kyushu University

### Educational Activity

- 【Bachelor Degree Program】School of Informatics and Data Science : Department of Informatics and Data Science
- 【Master's Program】Graduate School of Advanced Science and Engineering : Division of Advanced Science and Engineering : Informatics and Data Science Program
- 【Doctoral Program】Graduate School of Advanced Science and Engineering : Division of Advanced Science and Engineering : Informatics and Data Science Program

### Research Fields

- Informatics;Principles of Informatics;Theory of informatics

### Research Keywords

- hierarchy theorem
- computational complexity
- algorithm

### Affiliated Academic Societies

- The Institute of Electronics, Information and Communication Engineers, 1988
- Information Processing Society of Japan, 1990

## Educational Activity

### Course in Charge

- 2021, Liberal Arts Education Program1, 1Term, Elements of Calculus
- 2021, Liberal Arts Education Program1, 3Term, Linear AlgebraII
- 2021, Undergraduate Education, 1Term, Theory of Automata and Languages
- 2021, Graduate Education (Master's Program) , 1Term, Special Exercises on Informatics and Data Science A
- 2021, Graduate Education (Master's Program) , 2Term, Special Exercises on Informatics and Data Science A
- 2021, Graduate Education (Master's Program) , 3Term, Special Exercises on Informatics and Data Science B
- 2021, Graduate Education (Master's Program) , 4Term, Special Exercises on Informatics and Data Science B
- 2021, Graduate Education (Master's Program) , Academic Year, Special Study on Informatics and Data Science
- 2021, Graduate Education (Master's Program) , 3Term, Computational Complexity Theory
- 2021, Graduate Education (Doctoral Program) , Academic Year, Special Study on Informatics and Data Science

## Research Activities

### Academic Papers

- Some Properties of Homogeneous Pyramid Automata, IEICE Transactions on Information and Systems (Japanese Edition), J73-D-I(9), 778-780, 19900901
- RS-Vector Algorithms for Combinatorial Problems, IEICE Transactions on Information and Systems (Japanese Edition), J75-D-I(3), 143-151, 19920301
- Parallelizabilities of Vertex Set Partition Problems, Proceedings of the Joint Symposium on Parallel Processing, 92(1), 47-53, 19920601
- RS-Vector Algorithms for Combinational Problems, Systems and Computers in Japan, 24(7), 41-51, 19930701
- Finding Hamiltonian Circuits in Arrangements of Jordan Curves is NP-Complete, Proceedings of the Sixth Canadian Conference on Computational Geometry, 93-98, 19940801
- Extended Graph Connectivity and Its Gradually Increasing Parallel Complexity, Proceedings of the fifth Annual International Symposium on Algorithms and Computation (Lecture Notes in Computer Science), 834, 478-486, 19940801
- Finding Hamiltonian circuits in arrangements of Jordan Curves Is NP-complete, Information Processing Letters, 52, 183-189, 19941101
- On Problems with Gradually Increasing Parallel Complexities, Proceedings of the 1996 IEICE General Conference, 361-362, 19960301
- A Faster Parallel Algorithm for k-Connectivity, Proceedings of the Second Korea-Japan Joint Workshop on Algorithms and Computation, 8-13, 19960401
- Alpha-Connectivity: A Gradually Nonparallel Graph Problem, Journal of Algorithms, 20(3), 526-544, 19960501
- Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits, Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, 24-32, 19960501
- Time Lower Bounds Do Not Exist for CRCW PRAMs, Theoretical Computer Science, 155, 411-424, 19960601
- How Can We Demonstrate Increasing Parallel Complexities?, ACM/UMIACS Fourth Workshop on Parallel Algorithms, 19970501
- Time Complexity Hierarchies of Extended TMs for Parallel Computation, IEICE Transactions on Information and Systems (Japanese Edition), J80-D-I(5), 421-427, 19970501
- A Faster Parallel Algorithm for k-Connectivity, Information Processing Letters, 61, 265-269, 19970601
- (1+o(1))S(n)-Space Is Stronger Than S(n)-Space, Proceedings of the 3rd JAPAN-KOREA Joint Workshop on Algorithms and Computation, 72-79, 19970701
- A Canonical Form of Vector Machines, Information and Computation, 141(1), 37-65, 19980401
- Complexity Hierarchies on DLOGTIME-Uniform Circuits and TMs with Restricted Symbols, Proceedings of the Eleventh Workshop on Circuits and Systems in Karuizawa, 367-372, 19980401
- Improved Time and Space Hierarchies of One-Tape Off-Line TMs, Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (Lecture Notes of Computer Science), 1450, 580-588, 19980801
- Periodic Recession and R＆D Management in Japan, Proceedings of the IEEE EMS International Engineering Management Conference, 198-201, 19990501
- Space Hierarchies of Turing Machines with Restricted Tape Symbols, IEICE Transactions on Information and Systems (Japanese Edition), J82-D-I(6), 661-668, 19990601
- Technological Changes and the Effect of Business Cycles in Electric Manufacturing Companies for the Postwar 50 Years, Transactions of the Institute of Electrical Engineers of Japan (Japanese Edition), 119-A(6), 725-730, 19990601
- Juglar Cycles and Their Effects on Technological Changes, Portland International Conference on Management of Engineering and Technology, Proceedings Vol-1: Book of Summaries, Proceedings Vol-2: Papers Presented at PICMET’99, 1,2, 17-34, 19990701
- On Time-Constructible Functions in One-Dimensional Cellular Automata, Proceedings of the 12th International Symposium on Fundamentals of Computation Theory (Lecture Notes in Computer Science), 1684, 316-326, 19990801
- Universality of the Language Generating Ability of Two-Point Splicing Systems, IEICE Transactions on Information and Systems (Japanese Edition), J83-DI(1), 55-59, 20000101
- Application of Finite Difference Method to Arbitrary Mesh Points, Transactions of The Institute of Electrical Engineers of Japan (Japanese Edition), 120-A(2), 116-121, 20000201
- Complexity Hierarchies on Circuits under Restricted Uniformities, Proceedings of the 10th International Conference on Computing and Information (Lecture Notes in Computer Science), 2023, 20001101
- Speeding-Up Cellular Automata by Alternations, Proceedings of Machines Computations and Universality (Lecture Notes in Computer Science), 2055, 240-251, 20010501
- A three-dimensional uniquely parsable array grammar that generates and parses cubes, Electric Notes in Theoretical Comupter Science, 46, 1-16, 20010801
- Constructible functions in cellular automata and their applications to hierarchy results, Theoretical Computer Science, 270(1-2), 797-809, 20020106
- Computational Complexity in the Hyperbolic Plane, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (Lecture Notes in Computer Science), 2420, 365-374, 20020801
- Embedding a logically universal model and a self-reproducing model into number-conserving cellular automata, Proceedings of the Third International Conference on Unconventional Models of Computation (UMC2002) Lecture Notes in Computer Science), 2509, 164-175, 20021015
- A quadratic speedup theorem for iterative arrays, Acta Informatica, 38(11-12), 847-858, 20021101
- Self-reproduction and shape formation in two and three dimensional cellular automata with conservative constraints, Proceedings of the Eighth International Symposium on Artificial Life and Robotics (AROB2003), 377-380, 20030101
- Simulations between multi-dimensional deterministic and alternating cellular automata, Fundamenta Informaticae, 58(3-4), 261-271, 20031201
- A logically universal number-conserving cellular automaton with a unary table-lookup function, IEICE Transactions on Information and Systems, E87D(3), 694-699, 20040301
- Prefix computations on iterative arrays with sequential input/output mode, IEICE Transactions on Information and Systems, E87D(3), 708-712, 20040301
- Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs, Journal of Parallel and Distributed Computing, 64(3), 319-326, 20040301
- Time and space complexity classes of hyperbolic cellular automata, IEICE Transactions on Information and Systems, E87D(3), 700-707, 20040301
- Hierarchies of DLOGTIME-Uniform Circuits, M. Margenstern (ed.): Machines Computations and Universality (Proc. MCU 2004 Saint-Petersburg Russia= September 21-26= 2004) Lecture Notes in Computer Science, 3354, 211-222, 20050201
- Translational lemmas for alternating TMs and PRAMs, FUNDAMENTALS OF COMPUTATIONAL THEORY, Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (Lecture Notes in Computer Science), 3623, 137-148, 20050817
- A five-state von Neumann neighbor universal hyperbolic cellular automaton, Journal of Cellular Automata, 1(4), 275-297, 20061201
- A Time Hierarchy Theorem for Nondeterministic Cellular Automata, Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation (Lecture Notes in Computer Science), 4484, 511-520, 20070501
- Translational Lemmas for DLOGTIME-uniform Circuits, Alternating TMs, and PRAMs, Acta Informatica, 44(5), 345-359, 20070501
- Special Section on Foundations of Computer Science, IEICE Transactions on Information and Systems, E91-D(2), 161-161, 20080201
- A Java Based Three-Dimensional Cellular Automata Simulator and its Application to Three-Dimensional Larger Than Life, Proceedings of Automata 2008: Theory and Applications of Cellular Automata, Bristol, UK, Luniver Press, 413-416, 20080601
- A recursive padding technique on nondeterministic cellular automata, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E91A(9), 2335-2340, 20080901
- On the non-existence of rotation-symmetric von Neumann neighbor number-conserving cellular automata of which the state number is less than four, IEICE Transactions on Information and Systems, E92-D(2), 255-257, 20090201
- An Efficient Reconstruction Algorithm for Restricted Domino Tilings, IEICE Transactions on Information and Systems (Japanese Edition), J92-D(6), 758-766, 20090601
- Computational Complexity of Cast Puzzles, Proceedings of the 20th International Symposium on Algorithms and Computation (Lecture Notes in Computer Science), 5878, 122-131, 20091201
- On designing gliders in three-dimensional Larger Than Life cellular automata, F. Peper et al. (eds.): Natural Computing (Proceedings in Information and Communications Technology), 2, 184-190, 20100201
- A Tight Space-Hierarchy Theorem for Nondeterministic Turing Machines, IEICE Transactions on Information and Systems (Japanese Edition), J93-D(9), 1717-1726, 20100901
- NP-Hard and k-EXPSPACE-Hard Cast Puzzles, IEICE Transactions on Information and Systems, E93D(11), 2995-3004, 20101101
- Relationship between Depth and Nondeterministic Gates in Nondeterministic Circuit Families, IPSJ Journal (Japanese Edition), 5(4), 1667-1677, 20110401
- Computational Complexity of String Puzzles, Proceedings of the 18th Computing: the Australasian Theory Symposium (CRPIT, 128, Mestre, J. Eds., ACS.), 128, 69-74, 20120101
- Lower Bound of Face Guards of Polyhedral Terrains, Journal of Information Processing, 20(2), 435-437, 20120401
- A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem", Algorithms, 5(2), 261-272, 20120401
- Improved Lower and Upper Bounds of Face Guards of Polyhedral Terrains, Transactions on Information and Systems (Japanese Edition), J95-D(10), 1869-1872, 20121001
- Generalized Shisen-Sho is NP-Complete, IEICE Transactions on Information and Systems, E95D(11), 2712-2715, 20121101
- Finding the Minimum Number of Face Guards is NP-Hard, IEICE Transactions on Information and Systems, E95D(11), 2716-2719, 20121101
- Generalized Chat Noir is PSPACE-Complete, IEICE Transactions on Information and Systems, E96D(3), 502-505, 20130301
- Locating the Minimum Number of Guards with r-visibility in a Polyomino is NP-hard, The 16th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2013), 100-101, 20130901
- Generalized Pyramid is NP-Complete, IEICE Transactions on Information and Systems, E96D(11), 2462-2465, 20131101
- Universal von Neumann Neighborhood Cellular Automata on Penrose Tilings, Proceedings of the 1st International Workshop on Applications and Fundamentals of Cellular Automata, 515-521, 20131201
- Yosenabe is NP-complete, Journal of Information Processing, 22(1), 40-43, 20140101
- Computational Complexity of the r-visibility Guard Set Problem for Polyominoes, Lecture Notes in Computer Science, Springer-Verlag, 8845, 87-95, 20141101
- Computational Complexity of Generalized Forty Thieves, IEICE Transactions on Information and Systems, E98D(2), 429-432, 20150201
- Computational Complexity of Generalized Golf Solitaire, IEICE Transactions on Information and Systems, E98D(3), 541-544, 20150301
- Visibility Problems for Manhattan Towers, IEICE Transactions on Information and Systems, E99-D(3), 607-614, 20160301
- Computational Complexity of Building Puzzles, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E99-A(6), 1145-1148, 20160601
- Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-hard, IEICE Transactions on Information and Systems, E100-D(7), 1521-1525, 20170701
- NP-completeness of Mojipittan, IEICE Transactions on Information and Systems (Japanese Edition), J100-D(12), 974-977, 20171201
- Dosun-Fuwari is NP-complete, Journal of Information Processing, 26, 358-361, 20180401
- Herugolf and Makaro are NP-complete, Proceedings of the Ninth International Conference on Fun with Algorithms (FUN 2018), 100(24), 24:1-24:11, 20180613
- Computational Complexity of Usowan Puzzles, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101-A(9), 1537-1540, 20180901
- Kurotto and Juosan are NP-complete, The 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2018), 46-48, 20180901
- Nurimisaki and Sashigane are NP-complete, The 31st Canadian Conference on Computational Geometry (CCCG 2019), 184-194, 20190801
- Computational Complexity of Herugolf and Makaro, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E102-A(9), 1118-1125, 20190901
- Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles, IEICE Transactions on Information and Systems, E103-D(3), 500-505, 20200301
- Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons, The 14th International Conference and Workshop on Algorithms and Computation (R.M. Sohel et al.(Eds): WALCOM 2020, Lecture Notes in Computer Science), 12049, 146-157, 20200401
- Computational Complexity of Nurimisaki and Sashigane, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E103-A(10), 1183-1192, 20201001
- Chromatic Art Gallery Problem with r-visibility is NP-complete, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E104-A(9), 1-8, 20210901

### Publications such as books

- 2003/11, Quantum Computing, 2003, 11, Scholarly Book, Joint Translation, 9784627827912, 491
- 2010/02, Hierarchy Theorems, 2010, 02, Dictionary/Encyclopedia, Cocompilation, 3

### Invited Lecture, Oral Presentation, Poster Presentation

- How Can We Demonstrate Increasing Parallel Complexities?, Chuzo Iwamoto, ACM/UMIACS Fourth Workshop on Parallel Algorithms (WOPA1996), 1996/05, With Invitation, English, ACM/UMIACS, Philadelphia, USA
- Complexity Hierarchies on DLOGTIME-Uniform Circuits and TMs with Restricted Symbols, Chuzo Iwamoto, Eleventh Workshop on Circuits and Systems in Karuizawa, 1998/04, With Invitation, Japanese, Nagano
- Complexity Hierarchies on Turing Machines, Uniform Circuits, and Cellular Automata, Chuzo Iwamoto, Abstracts of Invited Lectures and Short Communications Delivered at the Ninth CNACSA, 2000/08, With Invitation, English, Bulgaria

### Awards

- 1993/03, Telecom-Columbus Award, Telecommunications Advancement Foundation, RS-Vector Algorithms for Combinatorial Problems
- 2008/01, 2007 LA/EATCS Best Presentation Award, LA Symposium, EATCS Japan Chapter, Reconstruction of Unicolored Domino Tilings of Degree Five from Orthogonal Projections
- 2009/11/26, The ISS Distinguished Service Award, President of IEICE Information and Systems Society, Contribution as an editor of IEICE Transactions on Information and Systems
- 2011/06, The ISS Distinguished Reviewer Award, President of IEICE Information and Systems Society, Contribution as a reviewer of IEICE Transactions
- 2018/02/06, 2017 LA/EATCS Best Presentation Award, LA Symposium, EATCS Japan Chapter, Herugolf is NP-complete