KASAI TAKUMI
| Emeritus Professor etc. | Emeritus Professor |
Researcher Information
Research Keyword
Educational Background
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 - 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 - Inherent ambiguity of languages generated by spine grammars
Kawaharada, I; T Kasai
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E88D, 6, 1150-1158, Jun. 2005, Peer-reviwed, There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.
Scientific journal, English - 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, In this paper, we will describe an algorithm which infers a Moore-type sequential machine from examples of inputs and outputs of an unknown Moore-type sequential machine. The hypothesis output by this inference algorithm is a nondeterministic Moore-type sequential machine which does not conflict with the given examples of inputs and outputs
we will show that the update time of the hypothesis will become a polynomial time of the sum of the lengths of the examples of inputs and outputs. Moreover, we will show that this inference algorithm will identify the Moore-type sequential machine in the limit by using the complete examples of inputs and outputs defined from the structures of the Moore-type sequential machine. © 2002 Wiley Periodicals, Inc.
Scientific journal, English - 転送スタック付きプッシュダウン・オートマトンと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 - 木－文字列変換機について
太田大輔; 川原田郁雄; 笠井琢美
電子情報通信学会技術研究報告, 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, SPRINGER VERLAG, 33, 1, 59-83, Jan. 2000, In this paper we introduce a restricted model of context-free tree grammars called spine grammars, and study their formal properties including considerably simple normal forms. Recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than context-free grammars, and for that reason tree adjoining grammars have been widely studied relating them to natural languages. It is shown that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. We also introduce accepters called linear pushdown tree automata, and show that linear pushdown tree automata accept exactly the class of tree languages generated by spine grammars. Linear pushdown tree automata are obtained from pushdown tree automata with a restriction on duplicability for the pushdown stacks.
Scientific journal, English - 順序機械の多項式時間推論アルゴリズム
高橋克彦; 藤芳明生; 笠井琢美
電子情報通信学会技術研究報告, 電子情報通信学会, 99, OMP99-52, 25-32, Nov. 1999
Research society, Japanese - 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, This paper describes a new tree structure called the left-right tree, along with its grammar and automaton, which form the theoretical basis for an English-Japanese machine translator developed by the authors. A left-right tree is a tree that differentiates between left children and right children. An English sentence is transformed into a set of left-right trees by labeling each node of the left-right tree with an English word. To represent a language, which is a collection of such left-right trees, we define a grammar for left-right tree languages, called the "tree categorical grammar." We also define the valenced pushdown transducer as a formalized model of the parser used in the translator. Due to the valence property of the symbols, the work of the stack is restricted in the pushdown transducer. We demonstrate the equivalence of the classes of left-right tree languages produced by different representations and explain some of the properties satisfied by the classes. © 1998 Scripta Technica.
Scientific journal, English - 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 - RELATIONS AMONG SIMULTANEOUS COMPLEXITY CLASSES OF NONDETERMINISTIC AND ALTERNATING TURING-MACHINES
S IWATA; T KASAI; E MORIYA
ACTA INFORMATICA, SPRINGER VERLAG, 30, 3, 267-278, May 1993, Peer-reviwed, Ruzzo [Tree-size bounded alternation, J. Comput. Syst. Sci. 21] introduced the notion of tree-size for alternating Turing machines (ATMs) and showed that it is a reasonable measure for classification of complexity classes. We establish in this paper that computations by tree-size and space simultaneously bounded ATMs roughly correspond to computations by time and space simultaneously bounded nondeterministic TMs (NTMs).
We also show that not every polynormal time bounded and sublinear space simultaneously bounded NTM can be simulated by any deterministic TM with a slightly increased time bound and a slightly decreased space bound simultaneously.
Scientific journal, English - SIMULTANEOUS (POLY-TIME, LOG-SPACE) LOWER BOUNDS
S IWATA; T KASAI
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 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, ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS, 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, SPRINGER VERLAG, 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, ASSOC COMPUTING MACHINERY, 31, 2, 361-376, 1984, Peer-reviwed
Scientific journal, English - SPACE COMPLEXITY IN ONLINE COMPUTATION
H MACHIDA; T KASAI
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS, 24, 3, 362-372, 1982, Peer-reviwed
Scientific journal, English - HOMOMORPHISMS BETWEEN MODELS OF PARALLEL COMPUTATION
T KASAI; RE MILLER
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS, 25, 3, 285-331, 1982, Peer-reviwed
Scientific journal, English - 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, ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS, 20, 1, 1-17, 1980, Peer-reviwed
Scientific journal, English - 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 - 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 - 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
