# Takumi Kasai

According to our database

^{1}, Takumi Kasai## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2005

Inherent Ambiguity of Languages Generated by Spine Grammars.

IEICE Transactions, 2005

2003

A polynomial time algorithm to infer sequential machines.

Systems and Computers in Japan, 2003

2000

Spinal-Formed Context-Free Tree Grammars.

Theory Comput. Syst., 2000

1998

Left-right trees, a new tree structure for machine translation.

Systems and Computers in Japan, 1998

1994

The Othello game on an n*n board is PSPACE-complete.

Theor. Comput. Sci., 1994

Thirty four Comparisons are Required to Sort 13 Items.

Proceedings of the Logic, 1994

1993

Relations among Simultaneous Complexity Classes of Nondeterministic and Alternating Turing Machines.

Acta Inf., 1993

1989

Probabilistic automata push-down.

Systems and Computers in Japan, 1989

1987

Simultaneous (Poly-Time, Log-Space) Lower Bounds.

Theor. Comput. Sci., 1987

1986

The emptiness problem for indexed language is exponential-time complete.

Systems and Computers in Japan, 1986

A Note on some Simultaneous Relations among Time, Space, and Reversal for Single Work Tape Nondeterministic Turing Machines

Information and Control, 1986

1985

Gradually Intractable Problems and Nondeterministic Log-Space Lower Bounds.

Mathematical Systems Theory, 1985

1984

Some Combinatorial Game Problems Require Omega(n

^{k}) Time.
J. ACM, 1984

1982

Space Complexity in On-Line Computation.

J. Comput. Syst. Sci., 1982

Homomorphisms between Models of Parallel Computation.

J. Comput. Syst. Sci., 1982

1981

Low Level Complexity for Combinatorial Games

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1980

A Characterization of Time Complexity by Simple Loop Programs.

J. Comput. Syst. Sci., 1980

On polynominal time computable problems.

Proceedings of the Graph Theory and Algorithms, 1980

1979

Classes of Pebble Games and Complete Problems.

SIAM J. Comput., 1979

A Theoretical Study of the Time Analysis of Programs.

Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

Comparing models of parallel computation by homomorphisms.

Proceedings of the IEEE Computer Society's Third International Computer Software and Applications Conference, 1979

1978

Classes of pebble games and complete problems.

Proceedings of the Proceedings 1978 ACM Annual Conference, 1978

1975

A Universal Context-Free Grammar

Information and Control, May, 1975

1974

Translatability of Flowcharts into While Programs.

J. Comput. Syst. Sci., 1974

1970

An Hierarchy Between Context-Free and Context-Sensitive Languages.

J. Comput. Syst. Sci., 1970