KASAI TAKUMI

Emeritus Professor etc.Emeritus Professor
Researcher Information

Degree

  • Doctor of Sciece, Kyoto University

Research Keyword

  • formal languages and automata
  • theory of computation
  • computitional complexity
  • 形式言語とオートマトン
  • 計算理論
  • 計算の複雑さ

Educational Background

  • Mar. 1971
    Waseda University, Graduate School, Division of Science and Engineering, 数学専攻
  • Mar. 1969
    Waseda University, Faculty of Science and Engineering, 数学科

Member History

  • 1996 - 1997
    コンピュテーション研究専門委員長, 電子情報通信学会, Society
Research Activity Information

Paper

  • Extended categorial grammars - A new formal grammatical model for machine translation
    Shunichi Matsubara; Takumi, Kasai
    The IEICE transactions on informantion and systems, The Institute of Electronics, Information and Communication Engineers, J92-D, 9, 1508-1517, Sep. 2009, Peer-reviwed, 本論文では,機械翻訳のための形式的な文法モデルとして拡張範疇文法を導入する.この文法は,現在開発が進められている英和機械翻訳機で使われている文法モデルである.近年の計算言語学では,tree adjoining grammarsと呼ばれる文法が,自然言語の形式的な文法モデルとして注目され,広く研究されている.今回,拡張範疇文法とtree adjoining grammarsの能力の一致が示される.
    Scientific journal, Japanese
    URL
  • A characterization of TALs by the generalized Dyck language
    Shunichi MATSUBARA; Takumi KASAI
    電子情報通信学会論文誌, The Institute of Electronics, Information and Communication Engineers, J90-D, 6, 1417-1427, Jun. 2007, Peer-reviwed, TALsは文脈自由言語よりも強力な記述能力をもつ言語のクラスであり,自然言語の形式化として近年注目を集めている.本論文では,任意のTALが認識可能集合と拡張Dyck言語と準同型写像によって特徴付けられることを示す.
    Scientific journal, Japanese
    URL
  • Inherent ambiguity of languages generated by spine grammars
    Kawaharada, I; T Kasai
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E88D, 6, 1150-1158, Jun. 2005, Peer-reviwed
    Scientific journal, English
    DOI URL
  • A polynomial time algorithm to infer sequential machines
    Katsuhiko Takahashi; Akio Fujiyoshi; Takumi Kasai
    Systems and Computers in Japan, 34, 1, 59-67, Jan. 2003, Peer-reviwed
    Scientific journal, English
    DOI URL
  • 転送スタック付きプッシュダウン・オートマトンとLinear Indexed Grammar について
    川原田 郁雄; 笠井 琢美
    電子情報通信学会論文誌, The Institute of Electronics, Information and Communication Engineers, J84-D1, 12, 1583-1590, Dec. 2001, Peer-reviwed, 本論文では, プッシュダウンオートマトンの自然な拡張である転送スタック付きプッシュダウンオートマトンを導入する.このオートマトンは, プッシュダウンスタックに加えて, このスタックと連動して動作する制限された補助スタックを転送スタックと呼ぶ.このオートマトンの能力について, 自然言語の形式化の一つである Linear Indexed Grammarとの比較を行い, 転送スタック付きプッシュダウンオートマトンで受理される言語のクラスが, Linear Indexed Grammarの言語のクラスと一致することを示す.
    Scientific journal, Japanese
    URL
  • 木－文字列変換機について
    太田大輔; 川原田郁雄; 笠井琢美
    電子情報通信学会技術研究報告, COMP2000-76, Mar. 2001
    Research society, Japanese
  • 順序機械の多項式時間推論アルゴリズム
    高橋克彦; 藤芳明生; 笠井琢美
    電子情報通信学会論文誌, J84-D-I, 1, 31-39, Jan. 2001
    Japanese
  • Linear Indexed Grammarと等価なオートマトンモデル
    川原田郁雄; 笠井琢美
    電子情報通信学会技術研究報告, COMP2000-57, Nov. 2000
    Research society, Japanese
  • 転送スタックつきプッシュダウン・オートマトン―関係代名詞を含む英文翻訳の構文解析モデル―
    川原田郁雄; 太田大輔; 笠井琢美
    電子情報通信学会技術研究報告, COMP99-92, 105-110, Mar. 2000
    Research society, Japanese
  • Spinal-formed context-free tree grammars
    A Fujiyoshi; T Kasai
    THEORY OF COMPUTING SYSTEMS, 33, 1, 59-83, Jan. 2000
    Scientific journal, English
  • 順序機械の多項式時間推論アルゴリズム
    高橋克彦; 藤芳明生; 笠井琢美
    電子情報通信学会技術研究報告, 電子情報通信学会, 99, OMP99-52, 25-32, Nov. 1999
    Research society, Japanese
    URL
  • Left-right trees: A new tree structure for machine translation
    Kouichi Kurokawa; Takumi Kasai
    Systems and Computers in Japan, John Wiley and Sons Inc., 29, 5, 84-91, 1998, Peer-reviwed
    Scientific journal, English
    DOI URL
  • Thirty four Comparisons are Required to Sort 13 Items
    Takumi Kasai; Shusaku Sawato; Shigeki Iwata
    Logic, Language and Computation, Lecture Notes in Computer Science, 792, 260-269, 1994, Peer-reviwed
    International conference proceedings, English
  • The Othello game on an n*n board is PSPACE-complete
    Shigeki Iwata; Takumi Kasai
    Theoretical Computer Science, 123, 2, 323-340, 1994, Peer-reviwed
    Scientific journal, English
    DOI URL
  • RELATIONS AMONG SIMULTANEOUS COMPLEXITY CLASSES OF NONDETERMINISTIC AND ALTERNATING TURING-MACHINES
    S IWATA; T KASAI; E MORIYA
    ACTA INFORMATICA, 30, 3, 267-278, May 1993, Peer-reviwed
    Scientific journal, English
    DOI URL
  • SIMULTANEOUS (POLY-TIME, LOG-SPACE) LOWER BOUNDS
    S IWATA; T KASAI
    THEORETICAL COMPUTER SCIENCE, 54, 2-3, 325-329, 1987, Peer-reviwed
    Scientific journal, English
  • A NOTE ON SOME SIMULTANEOUS RELATIONS AMONG TIME, SPACE, AND REVERSAL FOR SINGLE WORK TAPE NONDETERMINISTIC TURING-MACHINES
    E MORIYA; S IWATA; T KASAI
    INFORMATION AND CONTROL, 70, 2-3, 179-185, Aug. 1986, Peer-reviwed
    Scientific journal, English
  • GRADUALLY INTRACTABLE PROBLEMS AND NONDETERMINISTIC LOG-SPACE LOWER BOUNDS
    T KASAI; S IWATA
    MATHEMATICAL SYSTEMS THEORY, 18, 2, 153-170, 1985, Peer-reviwed
    Scientific journal, English
  • SOME COMBINATORIAL GAME PROBLEMS REQUIRE OMEGA(NK) TIME
    A ADACHI; S IWATA; T KASAI
    JOURNAL OF THE ACM, 31, 2, 361-376, 1984, Peer-reviwed
    Scientific journal, English
    DOI URL
  • SPACE COMPLEXITY IN ONLINE COMPUTATION
    H MACHIDA; T KASAI
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 24, 3, 362-372, 1982, Peer-reviwed
    Scientific journal, English
    DOI URL
  • HOMOMORPHISMS BETWEEN MODELS OF PARALLEL COMPUTATION
    T KASAI; RE MILLER
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 25, 3, 285-331, 1982, Peer-reviwed
    Scientific journal, English
    DOI URL
  • Low Level Complexity for Combinatorial Games
    Akeo Adachi; Shigeki Iwata; Takumi Kasai
    Proc. 13rd Ann. ACM Symp. on Theory of Computing, 228-237, 1981, Peer-reviwed
    Scientific journal, English
  • A CHARACTERIZATION OF TIME-COMPLEXITY BY SIMPLE LOOP PROGRAMS
    T KASAI; A ADACHI
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 20, 1, 1-17, 1980, Peer-reviwed
    Scientific journal, English
    DOI URL
  • Classes of pebble games and complete problems
    Takumi Kasai; Akeo Adachi; Shigeki Iwata
    SIAM Journal on Computing, 8, 4, 576-586, Nov. 1979, Peer-reviwed
    Scientific journal, English
    DOI URL
  • A Theoretical Study of the Time Analysis of Programs
    Akeo Adachi; Takumi Kasai; Etsuro Moriya
    Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 74, 201-207, 1979, Peer-reviwed
    International conference proceedings, English
  • A Universal Context-Free Grammar
    Takumi Kasai
    Information and Control, 28, 1, 30-34, 1975, Peer-reviwed
    Scientific journal, English
    DOI URL
  • Translatability of Flowcharts into While Programs
    Takumi Kasai
    Journal of Computer and System Sciences, 9, 2, 177-195, 1974, Peer-reviwed
    Scientific journal, English
  • An Hierarchy Between Context-Free and Context-Sensitive Languages
    Takumi Kasai
    Journal of Computer and System Sciences, 4, 5, 492-508, 1970, Peer-reviwed
    Scientific journal, English

Books and other publications

  • 計算の理論
    笠井琢美; 戸田誠之助
    Japanese, 共立出版, 1993
  • 計算量の理論
    笠井琢美
    Japanese, 近代科学社, 1987
  • 有限オートマトン入門
    岩田茂樹; 笠井琢美
    Japanese, 森北出版, 1986

Affiliated academic society

  • 電子情報通信学会
  • 日本数学会
  • EATCS