Katsushi INOUE


Sublogarithmic Space-Bounded Multi-Inkdot Alternating Turing Machines with Only Existential (Universal) States
Tsunehiro YOSHINAGA Jianliang XU Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5  pp. 1417-1420
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
multi-inkdot Turing machinesalternating Turing machinessublogarithmic space complexitycomplementation
 Summary | Full Text:PDF(94.3KB)

Inkdot versus Pebble over Two-Dimensional Languages
Atsuyuki INOUE Akira ITO Kunihiko HIRAISHI Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5  pp. 1173-1180
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
inkdotpebbletwo-dimensional automatanondeterminismalternation
 Summary | Full Text:PDF(260.1KB)

Path-Bounded One-Way Multihead Finite Automata
Satoshi INOUE Katsushi INOUE Akira ITO Yue WANG 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
Vol. E88-D  No. 1  pp. 96-99
Type of Manuscript:  Special Section LETTER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
one-way multihead finite automatasimple one-way multihead finite automatapath-bounded computationdegree of nondeterminism
 Summary | Full Text:PDF(92.5KB)

Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs
Hisao HIRAKAWA Katsushi INOUE Akira ITO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
Vol. E88-D  No. 1  pp. 31-38
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
two-dimensional tapethree-way deterministic finite automatarotated inputs
 Summary | Full Text:PDF(536.3KB)

Non-closure Property of One-Pebble Turing Machines with Sublogarithmic Space
Atsuyuki INOUE Akira ITO Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/05/01
Vol. E87-A  No. 5  pp. 1185-1188
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
one-pebble Turing machineclosure propertysublogarithmic space
 Summary | Full Text:PDF(103.1KB)

Some Observations on One-way Alternating Pushdown Automata with Sublinear Space
Jianliang XU Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/05/01
Vol. E87-A  No. 5  pp. 1012-1019
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
alternating pushdown automatasublogarithmic complexitysublinear complexityspace hierarchy
 Summary | Full Text:PDF(205.6KB)

On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space
Jianliang XU Yong CHEN Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/09/01
Vol. E86-D  No. 9  pp. 1814-1824
Type of Manuscript:  PAPER
Category: Theory of Automata, Formal Language Theory
Keyword: 
alternating pushdown automata1-inkdotalternation hierarchysublogarithmic complexity
 Summary | Full Text:PDF(298.1KB)

Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time
Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Vol. E86-A  No. 5  pp. 1207-1212
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
determinismnondeterminismself-verifying nondeterminismLas Vegasmulti-counter automata
 Summary | Full Text:PDF(183.8KB)

Some Properties on Input Head Reversal-Bounded Two-Dimensional Turing Machines
Masatoshi MORITA Katsushi INOUE Akira ITO Yue WANG 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/02/01
Vol. E86-D  No. 2  pp. 201-212
Type of Manuscript:  Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: Turing Machine, Recursive Functions
Keyword: 
two-dimensional Turing machineinput head reversal complexitydeterminism and nondeterminism
 Summary | Full Text:PDF(289.8KB)

A Note on Realtime One-Way Alternating and Deterministic Multi-Counter Automata
Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/02/01
Vol. E85-D  No. 2  pp. 346-349
Type of Manuscript:  Special Section LETTER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
alternating multi-counter automatadeterministic multi-counter automataone-way computationrealtime computationcomputational complexity
 Summary | Full Text:PDF(140.5KB)

Self-Verifying Nondeterministic and Las Vegas Multihead Finite Automata
Katsushi INOUE Yasunori TANAKA Akira ITO Yue WANG 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/05/01
Vol. E84-A  No. 5  pp. 1094-1101
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
determinismself-verifying nondeterminismLas Vegas(simple) multihead finite automata
 Summary | Full Text:PDF(253.2KB)

Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Turing Machines with Only Universal States
Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/01/01
Vol. E84-D  No. 1  pp. 61-64
Type of Manuscript:  Special Section LETTER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
alternating Turing machinesmulti-inkdottwo-way computationsublogarithmic space complexity
 Summary | Full Text:PDF(146.2KB)

A Note on Sensing Semi-One-Way Simple Multihead Finite Automata
Yue WANG Katsushi INOUE Akira ITO Tokio OKAZAKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/01/01
Vol. E84-D  No. 1  pp. 57-60
Type of Manuscript:  Special Section LETTER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
sensing functionsemi-one-way simple multi-head finite automatonhierarchy
 Summary | Full Text:PDF(136KB)

Some Observations on 1-Inkdot Alternating Multi-Counter Automata with Sublinear Space
Tsunehiro YOSHINAGA Jianliang XU Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/02/25
Vol. E83-D  No. 2  pp. 285-290
Type of Manuscript:  LETTER
Category: Theory of Automata, Formal Language Theory
Keyword: 
alternating multi-counter automata1-inkdot2-way computationsublinear space complexity
 Summary | Full Text:PDF(163.6KB)

Alternating Rebound Turing Machines
Lan ZHANG Jianliang XU Katsushi INOUE Akira ITO Yue WANG 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/05/25
Vol. E82-A  No. 5  pp. 745-755
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
alternating rebound Turing machinerebound automatonrebound counter automatonspace hierarchyclosure property
 Summary | Full Text:PDF(801.3KB)

A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space
Tokio OKAZAKI Lan ZHANG Katsushi INOUE Akira ITO Yue WANG 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1999/05/25
Vol. E82-D  No. 5  pp. 999-1004
Type of Manuscript:  LETTER
Category: Automata,Languages and Theory of Computing
Keyword: 
deterministic one-counter automataone-pebble off-line deterministic Turing machinesaccepting power
 Summary | Full Text:PDF(173.2KB)

On the Sensing Function of One-Way Simple Multihead Finite Automata
Yue WANG Katsushi INOUE Akira ITO Tokio OKAZAKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/11/25
Vol. E81-D  No. 11  pp. 1308-1311
Type of Manuscript:  LETTER
Category: Automata,Languages and Theory of Computing
Keyword: 
sensing functionone-way simple multihead finite automatonhierarchy
 Summary | Full Text:PDF(319.4KB)

A Note on Probabilistic Rebound Automata
Lan ZHANG Tokio OKAZAKI Katsushi INOUE Akira ITO Yue WANG 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/10/25
Vol. E81-D  No. 10  pp. 1045-1052
Type of Manuscript:  PAPER
Category: Automata,Languages and Theory of Computing
Keyword: 
probabilistic rebound automatonone-marker rebound automaton two-way nondeterministic one counter automatoncontext-free languageclosure property
 Summary | Full Text:PDF(682.1KB)

A Linear-Time Normalization of One-Dimensional Quadtrees
Akira ITO Katsushi INOUE Yue WANG 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/03/25
Vol. E81-D  No. 3  pp. 271-277
Type of Manuscript:  PAPER
Category: Algorithm and Computational Complexity
Keyword: 
quadtreenormalizationbinary stringlinear time
 Summary | Full Text:PDF(548.1KB)

Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space
Jianliang XU Katsushi INOUE Yue WANG Akira ITO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1997/12/25
Vol. E80-D  No. 12  pp. 1221-1226
Type of Manuscript:  LETTER
Category: Automata,Languages and Theory of Computing
Keyword: 
alternating pushdown automatainkdot-depthinkdot-sizespace hierarchy
 Summary | Full Text:PDF(485.7KB)

On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size
Jianliang XU Katsushi INOUE Yue WANG Akira ITO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1997/01/25
Vol. E80-D  No. 1  pp. 86-90
Type of Manuscript:  LETTER
Category: Automata,Languages and Theory of Computing
Keyword: 
alternating pushdown automatamulti-inkdotsublogarithmic space complexityleaf-size
 Summary | Full Text:PDF(428.7KB)

On Simple One-Way Multihead Pushdown Automata
Yue WANG Katsushi INOUE Akira ITO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/12/25
Vol. E79-D  No. 12  pp. 1613-1619
Type of Manuscript:  PAPER
Category: Automata,Languages and Theory of Computing
Keyword: 
simple multihead pushdown automatonone-way machinehierarchyKolmogorov complexity
 Summary | Full Text:PDF(675.4KB)

Sensing Two-Way Three Heads are Better than Two
Yue WANG Katsushi INOUE Akira ITO Tokio OKAZAKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/11/25
Vol. E79-D  No. 11  pp. 1593-1595
Type of Manuscript:  LETTER
Category: Automata,Languages and Theory of Computing
Keyword: 
sensing multihead finite automatontwo-way machinehierarchy
 Summary | Full Text:PDF(199.2KB)

A Note on Alternating Pushdown Automata with Sublogarithmic Space
Jianliang XU Katsushi INOUE Yue WANG Akira ITO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/04/25
Vol. E79-D  No. 4  pp. 259-270
Type of Manuscript:  PAPER
Category: Automata,Languages and Theory of Computing
Keyword: 
alternating pushdown automatasublogarithmic space complexityweakly versus strongly
 Summary | Full Text:PDF(1MB)

Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime
Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/08/25
Vol. E78-D  No. 8  pp. 929-938
Type of Manuscript:  PAPER
Category: Automata, Languages and Theory of Computing
Keyword: 
alternationrealtime computationone-way counter automataone-way stack-counter automatacomputational complexity
 Summary | Full Text:PDF(816.5KB)

A Note on One-way Auxiliary Pushdown Automata
Yue WANG Jian-Liang XU Katsushi INOUE Akira ITO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/06/25
Vol. E78-D  No. 6  pp. 778-782
Type of Manuscript:  LETTER
Category: Automata, Languages and Theory of Computing
Keyword: 
auxiliary pushdown automatonalternationone-way machineKolmogorov complexity
 Summary | Full Text:PDF(372.3KB)

Three-Dimensionally Fully Space Constructible Functions
Makoto SAKAMOTO Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/06/25
Vol. E77-D  No. 6  pp. 723-725
Type of Manuscript:  LETTER
Category: Artificial Intelligence and Cognitive Science
Keyword: 
multihead Turing machinethree-dimensional Turing machinespace complexityfully space constructible function
 Summary | Full Text:PDF(232.9KB)

Multihead Finite Automata with Markers
Yue WANG Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/04/25
Vol. E77-A  No. 4  pp. 615-620
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
multihead finite automatonmarker finite automatahierarchyone-letter alphabet
 Summary | Full Text:PDF(506KB)

Hierarchical Properties of Realtime One-Way Alternating Multi-Stack-Counter Automata
Tsunehiro YOSHINAGA Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/04/25
Vol. E77-A  No. 4  pp. 621-629
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
alternating automataone-way counterone-way stack-countercomputational complexity
 Summary | Full Text:PDF(741.4KB)

Leaf-Size Bounded Real-Time Synchronized Alternating One-Way Multicounter Machines
Hiroshi MATSUNO Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/03/25
Vol. E77-D  No. 3  pp. 351-354
Type of Manuscript:  LETTER
Category: Automaton, Language and Theory of Computing
Keyword: 
alternationsynchronized alternationmulticounter machine and real-time computation
 Summary | Full Text:PDF(327.9KB)

A Note on One-Way Multicounter Machines and Cooperating Systems of One-Way Finite Automata
Yue WANG Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1993/10/25
Vol. E76-D  No. 10  pp. 1302-1306
Type of Manuscript:  LETTER
Category: Automaton, Language and Theory of Computing
Keyword: 
one-way multicounter automatacooperating systems of one-way finite automatahierarchycomputational complexity
 Summary | Full Text:PDF(380.1KB)

Some Hierarchy Results on Multihead Automata over a One-Letter Alphabet
Yue WANG Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1993/06/25
Vol. E76-D  No. 6  pp. 625-633
Type of Manuscript:  PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
sensing multihead automataautomata on two-dimensional tapesone-letter alphabethierarchycomputational complexity
 Summary | Full Text:PDF(651.8KB)

A Two-Way Nondeterministic One-Counter Languages Not Accepted by Nondeterministic Rebound Automata
Makoto SAKAMOTO Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1990/06/25
Vol. E73-E  No. 6  pp. 879-881
Type of Manuscript:  LETTER
Category: Automaton, Language and Theory of Computing
Keyword: 
 Summary | Full Text:PDF(186.5KB)

A Note on Synchronized Alternating Turing Machines with Small Space Bounds
Katsushi INOUE Itsuo TAKANAMI Akira ITO Hiroshi MATSUNO 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1989/11/25
Vol. E72-E  No. 11  pp. 1182-1184
Type of Manuscript:  LETTER
Category: Automation, Language and Theory of Computing
Keyword: 
 Summary | Full Text:PDF(239KB)

Some Closure Properties of the Class of Sets Accepted by Three-Way Two-Dimensional Alternating Finite Automata
Akira ITO Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1989/04/25
Vol. E72-E  No. 4  pp. 348-350
Type of Manuscript:  LETTER
Category: Automation, Language and Theory of Computing
Keyword: 
 Summary | Full Text:PDF(215.2KB)

Some Realizations of Multi-Valued Logic Functions with Cellular Arrays
Itsuo TAKANAMI Katsushi INOUE 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1989/03/25
Vol. E72-E  No. 3  pp. 235-240
Type of Manuscript:  PAPER
Category: Computer Hardware and Design
Keyword: 
 Summary | Full Text:PDF(419.2KB)

Alternating Multihead Finite Automata with Constant Leaf-Sizes
Hiroshi MATSUNO Katsushi INOUE Itsuo TAKANAMI Hiroshi TANIGUCHI 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1988/10/25
Vol. E71-E  No. 10  pp. 1006-1012
Type of Manuscript:  PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
 Summary | Full Text:PDF(609.6KB)

A Note on Alternating Turing Machines Using Small Space
Akira ITO Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1987/10/25
Vol. E70-E  No. 10  pp. 990-996
Type of Manuscript:  PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
 Summary | Full Text:PDF(678.6KB)

A Note on Reversal Complexities of Real-Time Counter Machines
Hiroshi MATSUNO Katsushi INOUE Itsuo TAKANAMI Hiroshi TANIGUCHI 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1986/08/25
Vol. E69-E  No. 8  pp. 838-839
Type of Manuscript:  LETTER
Category: Automata and Languages
Keyword: 
 Summary | Full Text:PDF(128.8KB)

Alternating One-Way Multihead Turing Machines with Only Universal States
Shunichi SAKURAYAMA Hiroshi MATSUNO Katsushi INOUE Itsuo TAKANAMI Hiroshi TANIGUCHI 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1985/10/25
Vol. E68-E  No. 10  pp. 705-711
Type of Manuscript:  PAPER
Category: Automata and Languages
Keyword: 
 Summary | Full Text:PDF(577KB)

A Note on Space Complexity of Nondeterministic Two-Dimensional Turing Machines
Akira ITO Katsushi INOUE Itsuo TAKANAMI Hiroshi TANIGUCHI 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1983/08/25
Vol. E66-E  No. 8  pp. 508-509
Type of Manuscript:  LETTER
Category: Automata and Languages
Keyword: 
 Summary | Full Text:PDF(150.5KB)

A Note on Alternating On-Line Turing Machines with Only Universal States
Katsushi INOUE Itsuo TAKANAMI Hiroshi TANIGUCHI Akira ITO 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1983/06/25
Vol. E66-E  No. 6  pp. 395-396
Type of Manuscript:  LETTER
Category: Automata and Languages
Keyword: 
 Summary | Full Text:PDF(162.4KB)

Nonclosure Properties of Two-Dimensional On-Line Tessellation Acceptors and One Way Parallel Sequential Array Acceptors
Katsushi INOUE Akira NAKAMURA 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1977/09/25
Vol. E60-E  No. 9  pp. 475-476
Type of Manuscript:  LETTER
Category: Automata and Languages
Keyword: 
 Summary | Full Text:PDF(167.9KB)