Kenichi MORITA


Generalized Chat Noir is PSPACE-Complete
Chuzo IWAMOTO Yuta MUKAI Yuichi SUMIDA Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3  pp. 502-505
Type of Manuscript:  Special Section LETTER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
PSPACE-completecomputational complexitytwo-player gameChat Noir
 Summary | Full Text:PDF

Generalized Shisen-Sho is NP-Complete
Chuzo IWAMOTO Yoshihiro WADA Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/11/01
Vol. E95-D  No. 11  pp. 2712-2715
Type of Manuscript:  LETTER
Category: Fundamentals of Information Systems
Keyword: 
NP-completecomputational complexityone-player gameShisen-Sho
 Summary | Full Text:PDF

Finding the Minimum Number of Face Guards is NP-Hard
Chuzo IWAMOTO Yusuke KITAGAKI Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/11/01
Vol. E95-D  No. 11  pp. 2716-2719
Type of Manuscript:  LETTER
Category: Fundamentals of Information Systems
Keyword: 
face guardspolyhedral terrainsNP-hard
 Summary | Full Text:PDF

NP-Hard and k-EXPSPACE-Hard Cast Puzzles
Chuzo IWAMOTO Kento SASAKI Kenji NISHIO Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/11/01
Vol. E93-D  No. 11  pp. 2995-3004
Type of Manuscript:  PAPER
Category: Fundamentals of Information Systems
Keyword: 
computational complexityNP-hardk-EXPSPACE hardcast puzzle
 Summary | Full Text:PDF

On the Non-existance of Rotation-Symmetric von Neumann Neighbor Number-Conserving Cellular Automata of Which the State Number is Less than Four
Naonori TANIMOTO Katsunobu IMAI Chuzo IWAMOTO Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/02/01
Vol. E92-D  No. 2  pp. 255-257
Type of Manuscript:  Special Section LETTER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
cellular automatanumber-conservation
 Summary | Full Text:PDF

A Recursive Padding Technique on Nondeterministic Cellular Automata
Chuzo IWAMOTO Harumasa YONEDA Kenichi MORITA Katsunobu IMAI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/09/01
Vol. E91-A  No. 9  pp. 2335-2340
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
cellular automatacomputational complexityhierarchy theorem
 Summary | Full Text:PDF

A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function
Katsunobu IMAI Akihiko IKAZAKI Chuzo IWAMOTO Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/03/01
Vol. E87-D  No. 3  pp. 694-699
Type of Manuscript:  Special Section PAPER (Special Section on Cellular Automata)
Category: 
Keyword: 
cellular automatalogical universalitynumber-conservation
 Summary | Full Text:PDF

Prefix Computations on Iterative Arrays with Sequential Input/Output Mode
Chuzo IWAMOTO Tomoka YOKOUCHI Kenichi MORITA Katsunobu IMAI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/03/01
Vol. E87-D  No. 3  pp. 708-712
Type of Manuscript:  Special Section PAPER (Special Section on Cellular Automata)
Category: 
Keyword: 
prefix computationiterative arrayslanguage recognition
 Summary | Full Text:PDF

Simple Universal Reversible Cellular Automata in Which Reversible Logic Elements Can Be Embedded
Kenichi MORITA Tsuyoshi OGIRO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/03/01
Vol. E87-D  No. 3  pp. 650-656
Type of Manuscript:  INVITED PAPER (Special Section on Cellular Automata)
Category: 
Keyword: 
reversible cellular automatonreversible logic elementrotary elementuniversality
 Summary | Full Text:PDF

Uniquely Parallel Parsable Unification Grammars
Jia LEE Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/01/01
Vol. E84-D  No. 1  pp. 21-27
Type of Manuscript:  Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
uniquely parsable grammarunification grammarparallel parsingdeterministic parsing
 Summary | Full Text:PDF

Normal Forms for Uniquely Parsable Grammar Classes Forming the Deterministic Chomsky Hierarchy
Jia LEE Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/11/25
Vol. E83-D  No. 11  pp. 1917-1923
Type of Manuscript:  PAPER
Category: Theory of Automata, Formal Language Theory
Keyword: 
uniquely parsable grammarnormal formdeterministic Chomsky hierarchy
 Summary | Full Text:PDF

Computation-Universal Models of Two-Dimensional 16-State Reversible Cellular Automata
Kenichi MORITA Satoshi UENO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/01/25
Vol. E75-D  No. 1  pp. 141-147
Type of Manuscript:  Special Section PAPER (Special Section on Theoretical Foundations of Computing)
Category: 
Keyword: 
cellular automatareversibilitycomputation-universality
 Summary | Full Text:PDF

A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem
Kenichi MORITA 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1990/06/25
Vol. E73-E  No. 6  pp. 978-984
Type of Manuscript:  PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
 Summary | Full Text:PDF

Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata
Kenichi MORITA Masateru HARAO 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1989/06/25
Vol. E72-E  No. 6  pp. 758-762
Type of Manuscript:  PAPER
Category: Automation, Language and Theory of Computing
Keyword: 
 Summary | Full Text:PDF

A 1-Tape 2-Symbol Reversible Turing Machine
Kenichi MORITA Akihiko SHIRASAKI Yoshifumi GONO 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1989/03/25
Vol. E72-E  No. 3  pp. 223-228
Type of Manuscript:  PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
 Summary | Full Text:PDF

An Isometric Context-Free Array Grammar That Generates Rectangles
Yasunori YAMAMOTO Kenichi MORITA Kazuhiro SUGATA 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1982/12/25
Vol. E65-E  No. 12  pp. 754-755
Type of Manuscript:  LETTER
Category: Automata and Languages
Keyword: 
 Summary | Full Text:PDF

Space Complexity for Recognizing Connectedness of Three-Dimensional Patterns
Yasunori YAMAMOTO Kenichi MORITA Kazuhiro SUGATA 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1981/12/25
Vol. E64-E  No. 12  pp. 778-785
Type of Manuscript:  PAPER
Category: Automata and Languages
Keyword: 
 Summary | Full Text:PDF

Computing Abilities of Multi-Head and Finite-State Transducers
Kenichi MORITA Hiroyuki EBI Kazuhiro SUGATA 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1979/07/25
Vol. E62-E  No. 7  pp. 474-480
Type of Manuscript:  PAPER
Category: Automata and Languages
Keyword: 
 Summary | Full Text:PDF