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 】

2016.04

-

Now

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

Advanced Logic Synthesis
2019

Selected Topics in Computer and Information Science
2019

Logic Circuits
2019

Discrete Mathematics

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 】

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.
New Bounds for Quick Computation of the Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

T. Hirayama, R. Suzuki, K. Yamanaka, and Y. Nishitani

IEICE Trans. Information and Systems ( IEICE ) E107-D ( 8 ) 940 - 948 2024.08 [Refereed]

Bulletin of University, Institute, etc. Single Work

We present a time-efficient lower bound $\kappa$ on the number of gates in Toffoli-based reversible circuits that represent a given reversible logic function. $\kappa$ closely approximates $\sigmalb$, which is known as a relatively efficient lower bound in respect of evaluation time and tightness. The primary contribution of this paper is that $\kappa$ enables fast computation while maintaining a tightness of the lower bound, approximately equal to $\sigmalb$. We prove that the discrepancy between $\kappa$ and $\sigmalb$ is at most one only, by providing upper and lower bounds on $\sigmalb$ in terms of $\kappa$.

DOI
An Improved Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

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

Proc. 54th IEEE International Symposium on Multiple-Valued Logic 126 - 131 2024.05 [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. We carefully investigate cofactors of reversible functions to refine the characteristic vectors, and obtain a new theoretical basis for improving lower bounds. We show that the proposed lower bound $\upsilon$ is better than the previous lower bound $\sigmalb$ by making both mathematical and experimental comparisons.