Details of a Researcher - HIRAYAMA Takashi

HIRAYAMA Takashi

写真a

Affiliation	IWATE University Faculty of Science and Engineering Department of Science and Engineering Intelligence Information Course
Position	Lecturer

To the head of this page.▲

Research Interests 【 display / non-display 】

Logic minimization algorithms
Testing of logic circuits
Logic synthesis of VLSIs

To the head of this page.▲

Graduating School 【 display / non-display 】

　

-

1994.03

Gunma University Faculty of Engineering Computer Science Graduated

To the head of this page.▲

Graduate School 【 display / non-display 】

　

-

1996.03

Gunma University Graduate School, Division of Engineering Computer Science Master's Course Completed
　

-

1999.03

Gunma University Graduate School, Division of Engineering Electronics and Computer Science Doctor's Course Completed

To the head of this page.▲

Degree 【 display / non-display 】

Gunma University - Dr. Eng. 1999.01.01

To the head of this page.▲

Campus Career 【 display / non-display 】

2025.04

-

Now

IWATE University Faculty of Science and Engineering Department of Science and Engineering Intelligence Information Course Associate Professor [Duty]
2022.04

-

2025.03

IWATE University Faculty of Science and Engineering Department of Systems Innovation Engineering Studies in Computer, Intelligence and Media Sciences Associate Professor [Duty]
2016.04

-

2022.03

IWATE University Faculty of Science and Engineering Department of Systems Innovation Engineering Studies in Computer, Intelligence and Media Sciences Lecturer [Duty]
2009.04

-

2016.03

IWATE University Faculty of Engineering Department of Electrical Engineering, Electronics and Computer Science Lecturer [Duty]
2001.04

-

2009.03

IWATE University Faculty of Engineering Computer and Information Sciences Lecturer [Duty]

To the head of this page.▲

External Career 【 display / non-display 】

2000.04

-

2001.03

Ashikaga Institute of Technology Lecturer
1999.04

-

2000.03

Ashikaga Institute of Technology Research Assistant

To the head of this page.▲

Research Areas 【 display / non-display 】

Informatics / Computer system

To the head of this page.▲

Course Subject 【 display / non-display 】

2019

Advanced Logic Synthesis and Verification
2019

Selected Topics in Computer and Information Science
2019

Logic Circuits
2019

Discrete Mathematics
2019

Advanced Training

display all >>

To the head of this page.▲

Research Career 【 display / non-display 】

Study on Logic Synthesis of VLSIs Using Exclusive-OR Operations

Periods of research：

9999.01

-

Now

Keywords : Logic Synthesis,Excusive OR,VLSI

Style of Research： Collaboration in Organization

Research Program： (not selected)
Study on Logic Optimization Algorithms

Periods of research：

9999.01

-

Now

Keywords : Logic Optimization,Algorithm,Complexity

Style of Research： Collaboration in Organization

Research Program： (not selected)
Study on Easily Testable Realization of Logic Circuits

Periods of research：

9999.01

-

Now

Keywords : Logic Circuits,Easy Testability,Logic Synthesis

Style of Research： Collaboration in Organization

Research Program： (not selected)

To the head of this page.▲

Published Papers 【 display / non-display 】

Mystery Tower is Computationally Hard

K. Sangodo, K. Yamanaka, and T. Hirayama

Journal of Information Processing ( Information Processing Society of Japan ) 33 1092 - 1100 2025.12 [Refereed]

Bulletin of University, Institute, etc. Multiple authorship

We investigate the computational complexity of Mystery Tower, which is a 2D-platform action puzzle video game released by Namco in 1986 in Japan. First, we formalize Mystery Tower as a decision problem that asks whether or not, in a given level, the goal is reachable from the start. Our contributions are as follows. (1) We show the NP-hardness of the problem without an enemy character. (2) In the same problem setting as (1), we show that there exists an instance such that the length of its shortest solution is exponential. (3) If the use of enemy characters is allowed, the problem is PSPACE-complete.

DOI
An Improved Lower Bound on the Gate Count for Toffoli-Based Reversible Logic Circuits Realizing Given Reversible Functions

T. Hirayama, R. Endo, and K. Yamanaka

Journal of Multiple-Valued Logic and Soft Computing ( Old City Publishing ) 45 ( 1-3 ) 31 - 51 2025.07 [Refereed]

Bulletin of University, Institute, etc. Multiple authorship

This paper presents an improved lower bound, denoted as $\upsilon$, on the number of gates in Toffoli-based reversible circuits that realize a given reversible logic function. By carefully analyzing the cofactors of reversible functions, we refine the characteristic vectors and derive a new theoretical basis for improving lower bounds. We demonstrate that the proposed bound, $\upsilon$, surpasses the previous bound, $\sigma\mbox{-}lb$, through mathematical proofs and experimental comparisons.
Efficient Enumeration of Transversal Edge-Partitions

K. Shinraku, K. Yamanaka, and T. Hirayama

Discrete Applied Mathematics ( Elsevier ) 276 - 287 2025.01 [Refereed]

Bulletin of University, Institute, etc. Multiple authorship

An irreducible triangulation is a plane graph such that its outer face is a quadrangle, every inner face is a triangle, and it has no separating triangle. In this paper, we design an enumeration algorithm of all the transversal edge-partitions of an irreducible triangulation with $n$ vertices. The proposed algorithm enumerates them in $O(n)$-delay and $O(n^2)$-space after $O(n \log n)$-time preprocessing.

DOI
The Computational Complexity of Minimal Distance k-Dominating Set Enumeration

A. Ochi, K. Yamanaka, and T. Hirayama

Proc. 6th Workshop on Enumeration Problems and Applications 1 - 3 2024.10 [Refereed]

Bulletin of University, Institute, etc. Multiple authorship

We investigate the computational complexity of the problem of enumerating minimal distance k-dominating sets in a given graph. We prove that there exists an output-polynomial time algorithm that enumerates minimal distance k-dominating sets if there exists one that enumerates minimal dominating sets, and vice versa. As a consequence, Dom-Enum and Dist-k-Dom-Enum are equivalent.
Mystery Tower is Computationally Hard

K. Sangodo, K. Yamanaka, and T. Hirayama

Proc. 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games 47 - 48 2024.09 [Refereed]

Bulletin of University, Institute, etc. Multiple authorship

We investigate the computational complexity of Mystery Tower, which is an action puzzle video-game. First, we formalize Mystery Tower as a decision problem that asks reachability in each level from the start position to the exit. Our contributions are to show prove (1) the NP-hardness of the problem without enemy characters by reducing from 3-SAT problem, which is the best-known NP-complete problem, and (2) PSPACE-hardness of the problem if enemy characters are allowed.