Details of a Researcher - MORIYA, Etsuro

写真a

MORIYA, Etsuro

Affiliation

Faculty of Education and Integrated Arts and Sciences

Job title

Professor Emeritus

Degree

Dr. of Science ( Waseda University )

Homepage URL

http://www.edu.waseda.ac.jp/~moriya/

Research Experience

1995

-

　

Waseda University, Professor
1989

-

1995

Tokyo Woman's Christian University, Professor
1982

-

1989

Tokyo Woman's Christian University, Associate Professor
1979

-

1982

Tokyo Woman's Christian University, Assistant Professor
1971

-

1979

University of Electro-communications, Research Associate

Education Background

　

-

1970

Waseda University Faculty of Science and Engineering Department of Mathematics
　

　

　

Waseda University Graduate School, Division of Science and Engineering Mathematics

Professional Memberships

　

　

　

European Association for Theoretical Computer Science (EATCS)
　

　

　

Institute of Electrical and Electronics Engineers (IEEE)
　

　

　

Association for Computing Machinery (ACM)
　

　

　

Information Processing Society of Japan
　

　

　

The Institute of Electronics, Information and Communication Engineers (IEICE)
　

　

　

Mathematical Society of Japan

▼display all

Research Areas

Applied mathematics and statistics / Basic mathematics / Theory of informatics

Research Interests

Complexity, Algorithm, Automaton, Formal language, Code, Mathematics in General (incl.Probability Theory & Mathematical Statistics),Applied Mathematics,Theoretical Computer Science

Papers

情報オリンピック ─ 科学技術創造立国日本を担う人材の発掘育成とその課題

守屋悦朗

理科の教育 60 ( 706 ) 26 - 29 2011.05
ON ALTERNATING PHRASE-STRUCTURE GRAMMARS

Etsuro Moriya, Friedrich Otto

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 21 ( 1 ) 1 - 25 2010.02

　View Summary

The concepts of alternation and of state alternation are extended from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. For the resulting classes of alternating grammars the expressive power is investigated with respect to the leftmost derivation mode and with respect to the unrestricted derivation mode. In particular new grammatical characterizations for the class of languages that are accepted by alternating pushdown automata are obtained in this way.

DOI
未来のコンピュータ好きを育てる: 情報オリンピック ─ 国際科学オリンピックおよびプログラミングコンテストの紹介

守屋悦朗

情報処理 vol.50 ( No.10 ) 970 - 975 2009.10
On Alternating Phrase-Structure Grammars

E.Moriya, F.Otto

Lecture Notes in Computer Science Volume 5196 397 - 408 2008.09

DOI
Japanese Olympiad in Informatics

Seiichi Tani, Etsuro Moriya

Olympiads in Informatics Vol.2 163 - 170 2008.08

CiNii
Some additional remarks on grammatical characterizations of alternating PDAs

守屋悦朗, F.Otto

京都大学数理解析研究所講究録 1599 103 - 110 2008.05
On alternating non-context-free grammars

E.Moriya, F.Otto

Kasseler Informatikschriften ( 6/2007 ) 2007.11
Two ways of introducing alternation into context-free grammars and pushdown automata

Etsuro Moriya, Friedrich Otto

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E90D ( 6 ) 889 - 894 2007.06

　View Summary

Two ways of introducing alternation for context-free grammars and pushdown automata are compared. One is the usual way which combines '' states '' with alternation [1], [4],[7], and the other is the way used in [6] to define the alternating context-fret: grammar, i.e., alternation is governed by the variables of the grammar. In this paper the latter way is taken over to define a new type of alternating pushdown automaton by combining the '' pushdown symbols '' of the pushdown automaton with alternation. We have derived a characterization of the original alternating context-free grammars in terms of such a new type of alternating pushdown automaton without states. It is also shown that, if (non-alternating) states are introduced as an additional feature for this type of pushdown automaton, then the resulting alternating pushdown automaton has exactly the same expressive power as the original alternating pushdown automaton.

DOI
Alternating CFG の拡張について

守屋悦朗, F.Otto, H.Messerschmit

京都大学数理解析研究所講究録 1554, pp.9-15 2007
情報教育を履修漏れ問題から考える

オピニオン、WASEDA.COM on asahi.com 2006.12
CFG/PDL の alternation の付与方法ほかについて

守屋悦朗

京都大学数理解析研究所講究録 1489, pp.22-28 2006.05
CFG/PDL の alternation の付与方法ほかについて

京都大学数理解析研究所講究録 ( 1489 ) 22 - 28 2006.05
On counting and optimization variants of the subgraph connecting problem

D.Kawasaki, E.Moriya

Congressus Numerantium 175 53 - 63 2005.12
On state-alternating context-free grammars

E Moriya, D Hofbauer, M Huber, F Otto

THEORETICAL COMPUTER SCIENCE 337 ( 1-3 ) 183 - 216 2005.06

　View Summary

State-alternating context-free grammars are introduced, and the language classes obtained from them are compared to the classes of the Chomsky hierarchy as well as to some well-known complexity classes. In particular, state-alternating context-free grammars are compared to alternating context-free grammars (Theoret. Comput. Sci. 67 (1989) 75-85) and to alternating pushdown automata. Further, various derivation strategies are considered, and their influence on the expressive power of (state-) alternating context-free grammars is investigated. (c) 2005 Elsevier B.V. All rights reserved.

DOI
教育の情報化と情報教育 ─ 進展?と展望?

早稲田大学教育総合研究所所報 ( 39 ) 27 - 30 2005.06
More2 on the subgraph connecting problem - Counting and optimization variants and their complexity

E.Moriya, D.Kawasaki

Tech. Rept. , Adv. Res. Inst. for Sci. and Engg., Waseda Univ. No.05-04 2005.05
A tentative approach to 2-dimensional theory of DNA computation

E.Moriya, M.Moriyama

早稲田大学教育学部「学術研究」(数学篇) 53 1 - 18 2005.02
More on the subgraph connecting problem -- New Variants and their completeness,

E.Moriya

Congressus Numerantium 169 211 - 222 2004.12
On alternating context-free grammars -- Old and new versions and their characterizations

E.Moriya

京都大学数理解析研究所講究録 ( 1375 ) 92 - 98 2004.05
A graph problem deriving various complete variants for several complexity classes

T.Nishida, E.Moriya

Tech. Rept. , Adv. Res. Inst. for Sci. and Engg., Waseda Univ. No.2004-02 2004.04
部分グラフ連結化問題による計算量の階層

西田泰士, 守屋悦朗

信学技報 Comp2003-69 ( 69 ) 2004.01
On state-alternating context-free grammars -- with detailed proof and supplementary results

E.Moriya, D.Hofbauer, M.Huber, F.Otto

Tech. Rept., Adv. Res. Inst. for Sci. and Engg., Waseda Univ. No.2003-5 2003.11
Shrinking alternating two-pushdown automata

F.Otto, E.Moriya

京都大学数理解析研究所講究録 ( 1325 ) 191 - 196 2003.05
On the space complexity of turn bounded pushdown automata

E Moriya, T Tada

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 80 ( 3 ) 295 - 304 2003.03

　View Summary

A pushdown automaton is said to make a turn at a given instant if it changes at that instant from stack increasing to stack decreasing. Let NPDA-TURN(f(n)) and DPDA-TURN(f(n)) denote the classes of languages accepted by nondeterministic and deterministic pushdown automata respectively that make at most f(n) turns for any input of length n. In this paper the following inclusions that express the space complexity of turn bounded pushdown automata are given: DPDA-TURN(f(n)) subset of or equal to DSPACE(logf(n) log n), and NPDA-TURN(f(n)) subset of or equal to NSPACE (logf(n) log n). In particular, it follows that finite-turn pushdown automata are logarithmic space bounded: DPDA-TURN(O(1)) subset of or equal to DL and NPDA-TURN(O(1)) subset of or equal to NL, from which two corollaries follow: one is that the class of metalinear context-free languages is complete for NL, and the other is that a more tight inclusion NPDA-TURN(f(n)) subset of or equal to DSPACE(log(2)f(n) log n) cannot be derived unless DL = NL, though NPDA-TURN (f(n)) subset of or equal to DSPACE(log(2)f(n) log(2) n) holds.

DOI
重み付きグラフの最大マッチングを求める並列近似アルゴリズム

兼村賢治, 守屋悦朗

信学技報 102 ( 343 ) 49 - 56 2002.09
Parallel approximation algorithms and average-time analysis for maximum weighted matching in general graphs

K.Kanemura, E.Moriya

Tech. Rept., Adv. Res. Inst. for Sci. and Engg., Waseda Univ, No.2002-3 2002.05
Parallelization in extended μ-H systems and its universality

K.Shirakata, E.Moriya

Congressum Numerantium 151 85 - 95 2001
On the space complexity of turn bounded pushdown automata

E.Moriya, T.Tada

3rd Internat'l Colloq. on Words, Languages, and Combinatorics 2000.03
On learning lexical functional grammars

E.Moriya

Selected Papers from AILA'99 Tokyo 2000
Chomsky hierarchy, the past and the present-from string grammars to tree grammars-

E.Moriya

Selected Papers from AILA'99 Tokyo 2000
第4回『教育の現場に活かすコンピュータ講座』数学コース報告

コロキウム 28, p.5 1999.12
スタック反転数限定PDAのSpace Complexity

信学技報 COMP99; 1999.12
Chomsky hierarchy, the past and the present

E.Moriya

AILA'99 Tokyo, Program & Abstracts 142 - 143 1999.08
高校数学においてプログラミングは必要か?

早稲田教育評論 13; 1, pp.209-232 1999.03
Turn bounded pushdown automata revisited

E.Moriya

Southeastern Intern'l Conf. on Combinatorics, Graph Theory, and Computing/ Florida Atlantic University 30, p.26 1999.03
Turn bounded pushdown automata revisited

E.Moriya

Congressus Nemerantium 138 65 - 77 1999
Optimally fast shortest paths algorithms for some classes of graphs

E.Moriya, K.Tsugane

International Journal of Computer Mathematics 70 293 - 317 1999
A generalization of finite-turn pushdown automaton languages and LOGCFL

E.Moriya, Y.Ohki

Gakujutsu Kenkyu, Sohool of Education Waseda University 47 ( 47 ) 17 - 28 1999

CiNii
情報教育の現状と展望

早稲田教育評論/教育総合研究所 12; 75, pp.27-86 1998.04
あるNP最適化問題の近似可能性について

信学技報/電子情報通信学会 COMP97;116,pp79-84 1998.03
LOGCFLのある部分クラスについて

信学技報/電子情報通信学会 COMP97;115,pp71-77 1998.03
A generalization of finite-turn pushdown automaton languages and LOGCFL

E.Moriya, Y.Ohki

学術研究(数学篇) 47 ( 47 ) 17 - 28 1998.02

CiNii
Optimally fast shortest path algorithms for some classes of graphs

E Moriya, K Tsugane

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 70 ( 2 ) 297 - 317 1998

　View Summary

Two algorithms for shortest path problems are presented. One is to find the all-pairs shortest paths (APSP) that runs in O(n(2)logn+nm) time for n-vertex m-edge directed graphs consisting of strongly connected components with O(logn) edges among them. The other is to find the single-source shortest paths (SSSP) that runs in O(n) time for graphs reducible to the trivial graph by some simple transformations. These algorithms are optimally fast for some special classes of graphs in the sense that the former achieves O(n(2)) which is a lower bound of the time necessary to find APSP, and that the latter achieves O(n) which is a lower bound of the time necessary to find SSSP. The latter can be used to find APSP, also achieving the running time O(n(2)).
中高教員のリカレント教育

早稲田フォーラム/早稲田大学 ;75,pp36-43 1998.01
チューリングマシンと計算量の理論

培風館 261pp 1997.11
計算のむずかしさとは何か

math OLYMPIAN ;9,11-38 1997.10
数学教育とコンピュータ

学文社 253pp 1997.07
最適な最短経路アルゴリズムを持つグラフのクラスについて

信学技報/電子情報通信学会 COMP97;7,pp49-56 1997.04
Grammatical characterizations of alternating pushdown and linear-bounded automata

「学術研究」/教育学部 45 1997.02
コンピュータを利用した数学教育

「コロキウム」/早稲田大学教育総合研究室 22 1996.11
ある種のグラフに対する最短経路アルゴリズム

電子情報通信学会基礎理論ワークショップ論文集/電子情報通信学会 1996.07
Variants of alternating grammars

京都大学数理解析研究所講究録 943 1996.04
第7回国際情報オリンピックオランダ大会

bit/共立出版 28;1 1996.01
パソコンで数学(下)

共立出版 1995.12
パソコンで数学(上)

共立出版 1995.07
第2回日本情報オリンピック問題と解説

bit/共立出版 27;6 1995.06
STACK TREE AUTOMATA AND THEIR RELATION TO CONTEXT-FREE GRAMMARS WITH MEMORY

E MORIYA

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E77D ( 10 ) 1086 - 1093 1994.10

　View Summary

As a generalization of the tree automation, tree automata with various types of memory are introduced and their relation to context-free grammars with memory is studied. Relations between computation trees of tree automata with memory and derivation trees of context-free grammars with memory are established, and as a consequence, the languages generated by context-free grammars with memory are characterized in terms of the sets of trees recognizable by tree automata with memory. Also various types of traversal of labeled trees recognizable by tree automata with memory are considered.
On two-way tree automata

E.Moriya

Information Processing Letters 50 117 - 121 1994

DOI
RELATIONS AMONG SIMULTANEOUS COMPLEXITY CLASSES OF NONDETERMINISTIC AND ALTERNATING TURING-MACHINES

S IWATA, T KASAI, E MORIYA

ACTA INFORMATICA 30 ( 3 ) 267 - 278 1993.05

　View Summary

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.

DOI
CONTEXT-FREE GRAMMARS WITH MEMORY

E MORIYA

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E75D ( 6 ) 847 - 851 1992.11

　View Summary

CFGs (context-free grammars) with various types of memory are introduced and their generative capacities are investigated. For an automata-theoretic characterization, a new type of automaton called partitioning automaton is introduced and it is shown that the class of languages generated by CFGs with memory type X is equal to the class of languages accepted by partitioning automata of type X.
A GRAMMATICAL CHARACTERIZATION OF ALTERNATING PUSHDOWN-AUTOMATA

E MORIYA

THEORETICAL COMPUTER SCIENCE 67 ( 1 ) 75 - 85 1989.09

DOI
HICHART-a hierarchical flow chart description language

E.Moriya, T.Yaku, K.Futatsugi

Proc. 11th Ann. Interntl. Computer Software and Applications Conf. 157 - 163 1987
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 1986.08
A version of the NC=? SC Problem

E.Moriya, S.Iwata, T.Kasai

Congressus Numerantium 53 263 - 276 1986
A class of loop programs and time analysis

A.Adachi, T.Kasai, E.Moriya

Proc. 6th IBM Symp. Math. Found. Comput. Sci. 6 77 - 102 1981
A theoretical study on the time analysis of programs

A.Adachi, T.Kasai, E.Moriya

Lecture Notes in Computer Science 74 201 - 208 1979
Characterization theorems on abstract families of transducers

E.Moriya

Information Sciences 9 ( 3 ) 227 - 238 1975

DOI
Some remarks on state grammars and matrix grammars

E.Moriya

Information and Control 22 ( 2 ) 139 - 162 1973
Associate languages and derivational complexity of formal grammars and languages

E.Moriya

Information and Control 22 ( 2 ) 139 - 162 1973
Notes on state grammars operating under the free interpretation

E.Moriya

Rept. of Univ. Electro-comm. 23 ( 1 ) 63 - 72 1972

▼display all

Books and Other Publications

電子情報通信学会編『知識ベース』 (分担執筆第2編第1章)

守屋悦朗

オーム社 2009
情報・符号・暗号の理論

守屋悦朗

サイエンス社 2007.11
離散数学入門

守屋悦朗

サイエンス社 2006.06
高等学校検定教科書「高等学校数学A」「高等学校数学B」「高等学校数学C」「高等学校数学I」「高等学校数学II」「高等学校数学III」

伊藤隆一編

桐原書店 2003
数学辞典第4版分担執筆「情報科学における数学: 形式言語とオートマトン」

岩波書店 2003
形式言語とオートマトン

サイエンス社 2001.07
チューリングマシンと計算量の理論

培風館 1997.11
数学教育とコンピュータ

学文社 1997.07
パソコンで数学〔下〕

野口廣, 守屋悦朗

共立出版 1995.12
パソコンで数学〔上〕

野口廣, 守屋悦朗

共立出版 1995.07
コンピュータサイエンスのための離散数学

サイエンス社 1992
最近の計算理論

近代科学社 1976

▼display all

Research Projects

発展方程式の解の構造の研究

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
代数多様体の交叉の研究

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
アルゴリズムと計算量の研究

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
3次元・4次元多様体の位相幾何学的研究

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
最大作用素とそれに関連する作用素

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
非可逆現象を記述する方程式の研究

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
射影空間に於ける部分多様体の研究

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
非可逆現象を記述する方程式の研究

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
多様体の位相幾何学的研究

科学研究費助成事業(東京女子大学) 科学研究費助成事業(一般研究(C))
On the power of alternation in formal grammars and automata
An computer scientific approach to natural language study based on the lexical functional grammar
Studies on formal semantics and inference systems for natural language study

▼display all

Overseas Activities

形式言語理論・オートマトン理論の新展望

2011.09

-

2012.09

ドイツカッセル大学
計算量理論の観点から見た形式言語・オートマトン理論の研究

2000.09

-

2001.08

ドイツカッセル大学

Internal Special Research Projects

並列書き換え系の研究　－　特に、並列構文解析とその応用

2009

　View Summary

　研究代表者は従来から、並列計算の概念、とくに交代性（alternation）という概念を、所謂Chomsky階層と呼ばれる形式文法の各クラスやオートマトンのクラスになどに導入し、その記述能力・計算能力について研究を行なってきた。本特定課題研究では、形式文法の中でも実用的にも重要な文法のクラスである文脈自由文法（CFG）に交代性を導入したalternating CFGの構文解析法とその応用について研究することを目的とした。　「交代性」の概念はA.K.Chandra, D.C.Kozen, L.J.Stockmeyer (“Alternation,” J. Assoc. Comput. Mach. 28, 114-133, 1981）によって並列計算の概念の１つとしてTuring machineに対して初めて導入された。研究代表者は、1989年の論文E.Moriya, A grammatical characterization of alternating pushdown automata, Theor. Comput. Sci. 67, pp.75-85, 1989において交代性の概念を形式文法に初めて導入した。その後、肯定性の概念を導入した文法やオートマトンの研究を進め、多くの研究成果を発表している。特に、2010年発表の論文E.Moriya and F.Otto, On Alternating Phrase-Structure Grammars, International J. Foundations of Comput. Sci., Vol.21, pp.1-25, 2010. において、研究はかなり進展したにもかかわらず、交代性文法の生成能力が完全に解明されたわけではない。多くの未解決問題が残っているし、まったくの手付かずの課題もある。その１つに、交代性を導入した書き換え系（特に alternating CFG）の構文解析法の開発がある。実用的にも重要な文法であるCFGについては、様々な構文解析アルゴリズムが知られている。CFGの非終端記号は名詞、動詞、名詞句、名詞節、文などの文法的カテゴリーを表すものと考えられるので、その非終端記号に交代性を導入したalternating CFGにおいては、「交代性非終端記号」は、それに対応する文法的カテゴリーが複数の意味をもつ場合を表現するものと考えることができる。そのような見地から、alternating CFGの構文解析法を研究することを本特定課題研究の目標の1つとした。現在までに得られた成果の１つは、E.Moriya and F.Otto, Syntax analysis for alternating context-free grammars, preprint, 2009.である。良く知られている(交代性のない)CFGに対する構文解析法では、文法から消去ルールをなくすこと(ε-free CFGに変換すること)が前提となる。この論文では、交代制の入ったalternating CFGにおいて消去ルールをなくすことを証明するための前提として、alternating CFG Gが生成する言語 L(G) が空語εを含むか否かを判定する問題が決定可能であることを証明した。しかし、alternating CFGから消去ルールをなくすまでの道のりはまだ遠いように思われる。当面、CFGのサブクラスに交代制を導入した場合について、その構文解析法を開発する研究を継続して進めたい。
計算量の階層を特徴付ける単一問題の研究

2006

　View Summary

　研究代表者は従来より、ある組合せ論的問題１つから様々な変形版が自然に導入でき、しかもそれらが計算量の階層の中でも重要ないくつものクラスの完全問題になるようなものを発見することを目指してきた。Ｌ⊆ＮＬ⊆Ｐ⊆ＮＰ⊆ＰＳＰＡＣＥ⊆ＥＸＰ⊆ＮＥＸＰ⊆・・・といった計算量の階層のいくつかに対する完全問題を自然に導く組合せ論的問題の例としてはＳＡＴやＨＣＰ、あるいはAdachi-Iwata-Kasaiによる有効グラフ上の石置きゲームに関する結果[2] A.Adachi, S.Iwata and T.Kasai, Classes of pebble games and complete problems, SIAM J. Comput. 8 (1979), 574--586.等が知られているが、単にこういった決定問題に対する計算量の階層の各クラスを表すような変形版が自然に導入できるというにとどまらず、数え上げ版や最適化版（近似問題版）の計算量の各クラス、例えば、＃Ｐ，ＡＰＸ，ＮＰＯ，ＰＴＡＳ，ＦＰＴＡＳといったクラスをも表わすような１つの組合せ論的問題を発見することが目標であった。具体的には、研究代表者自らの先駆的研究T.Nishida and E.Moriya, Variants of the subgraph connecting problem and their computational complexity, Tech. Rept. of IEICE 103, 2004, 1－7.を出発点とし、すでに当初目標に沿ったいくつかの成果をあげてきた。その元となっている問題 "Subgraph Connecting Problem" とは、グラフ G とその部分グラフのいくつかが与えられたとき、各部分グラフと1点だけを共有して連結な G の部分グラフを求める問題である。本研究では近似問題のうちでまだ具体例が知られていなかったＰＴＡＳおよびＦＰＴＡＳに属す問題を見つけた。それは、グラフ G=(V,E) とその部分グラフ G1, ・・・, Gm, 頂点に対する重み関数 w : V(G)→N と定数 k∈N が与えられたとき、|V(G')∩V(Gi)|>0 for ∀i かつ ∑v∈V(G')w(v)≦k という条件の下で頂点の重みの和が最小となるような G の部分グラフ G' を求める問題である。なお、本研究の基礎ともなるオートマトン・言語理論にも取り組み、alternation （交代性）の概念を取り入れた形式文法とその拡張にに関しても成果を挙げた。
形式文法・オートマン理論における計算量理論的再考察

2003 Friedrich Otto

　View Summary

　本研究は、形式言語理論およびオートマトン理論におけるいくつかの問題を計算量理論的視点から再考察することを目指したものである。ドイツ・カッセル大学のOtto教授との国際共同研究である。　主たる研究目標は、並列計算の概念、とくに、もともとオートマトン理論において導入された「交代性(alternation)」という概念を形式文法にも導入し、従来の形式文法とオートマトンとの間に成り立っていた相関関係が交代性の導入によってどのように変わるのかを明らかにすることにあった。守屋により1989年に導入されたalternating CFG（以下、ACFGと略記する）は、alternationを持たない従来のCFGと等価であるプッシュダウンオートマトンにalternationを持たせたalternating PDA（以下、APDAと略記）を特徴付けることを目指したものであったが、当時は成功するに至らなかった。本研究では、ACFGの新しいバージョンであるstate-alternating CFG（以下、state-ACFGと略記）を導入することにより、この特徴づけに成功した。これは、O.H.Ibarra - T.Jiang - H.WangによるACFGの変形版によるAPDAの特徴づけよりもずっと自然で美しいものである。また、この新しいstate-ACFGは従来のACFGよりも言語生成能力が高いこと（真に高いかどうかは未解決）、先に導入したACFGはAPDAの特殊ケースとして特徴付けられることも示すことができた。これらの成果により、APDAをalternationをもつCFGにより特徴付けるという当初の目標はようやく解決された。本研究では、こういったメインな結果以外にも、ACFGおよびstate-ACFGに関する基本的性質について研究成果を挙げることができた。　また、交代性の概念を導入したshrinking two-pushdownオートマトンの言語受理能力についての研究も行ない、文脈依存言語のクラスに含まれる等の基本的結果を得た。　主たる目標を支える基礎研究として並行して研究を行なったのが、グラフアルゴリズムの計算量の研究である。１つの決定問題から多くの特殊形が自然に導かれ、それらがいろんな計算量のクラスに対する完全問題になるという例は多くは知られていない。そのような新しい例として、グラフとそのその部分グラフに関するある種の問題を考え、それがさまざまな特殊形を自然に導き、しかも５つの主要な計算量のクラス NL, P, NP, PSPACE, NEXPに対する完全問題になることを示した。　また、グラフのマッチング問題に関する並列近似アルゴリズムを提案し、その計算量について考察した。
語彙機能文法をベースとした自然言語研究への計算機科学的アプローチ

2000 原田　康也, 中野　美知子

　View Summary

　語彙機能文法（LFG: Lexical Functional }Grammar）は自然言語の構文・意味論の研究において有力な文法理論として言語学の観点のみならず数理的な観点からも多くの研究がなされている文法理論の１つである。本研究ではＬＦＧというフレームワークの有効性を明らかにすることを目指し、（１）その記述能力を形式言語・オートマトン理論の観点から明らかにすること、（２）人間の言語能力獲得に関するＬＦＧにもとづいたモデルの研究、（３）言語学で最近提案された意味表記のための言語とＬＦＧとの比較研究、などを中心に研究を進めてきた。　（１）に関する成果はすでに守屋の論文や国際会議での講演として発表したが、今後はＬＦＧのサブクラス、特にmildly context-sensitive languageと呼ばれる、言語学的にも数理的にも多くの等価な文法を持つクラスを中心に研究を進める予定である。とりわけ、tree automatonによる特徴付けは有用であると考えている。（２）および（３）に関する成果は中野および原田の論文や国際会議での講演としてすでにその一部分を発表した。特に、１９９９年には第１２回World Congress of Applied Linguisticsにおいて「LFG and its Computational Implications」と題する特別シンポジウムを本研究の共同研究者と電気通信大学の西野哲朗助教授とで共同主催し、LFGの提唱者であるStanford大学のJ.Bresnan教授やその共同研究者であるR.M.Kaplan、P.Sells両博士を招いて、研究発表と有意義な討論を行なった。これらをはじめとする現在進行中の成果は、以下に示した論文とは別に今後発表する予定である。
未定項表現を用いた形式意味論と推論体系の研究

1998 中野　美知子, 原田　康也, 西野　哲朗

　View Summary

　本研究では、これまで計算機科学者および言語学・応用言語学者がそれぞれ独自の理論に基づいて研究していた自然言語解析の様々なアプローチを、両分野の研究者が協力して双方の立場から検討した。　1997年度には7回の研究会を開催し、形式的意味論の観点から、線形論理（Linear Logic）を応用したGlue LanguageおよびICOTで開発された知識表現言語QUIXOTEについて検討した。Glue Languageは最近の語彙機能文法に基づいているため、1997年までに発表されていた線形論理の応用を1982年の古典的な語彙機能文法の枠組みに適用すると様々な発話状況により異なる読みの違いを反映させることができる等の知見を得た。一方、線形論理そのものは、命題論理に制限しても決定不能、推論規則をごく限られたものに限定してもなおNP困難である等、強力すぎることが分かった。　そこで、1998年度は、従来の語彙機能文法を制限した西野の提案になる上昇型語彙機能文法を取り上げ、1998年に提案された語彙機能文法の文生成の枠組みであるOptimal Syntaxについて検討した。1998年度は8回の研究会を持ち、Optimal Syntaxについては、西野がL.G.Valiantの提案したニューロイダルネットを用いてプログラム作成と計算機科学の立場からの問題点を検討し、中野は中学生のbe-動詞の文法判断にOptimal Syntaxの分析と整合性があるかどうかを検討し、守屋が推論過程を数学的に吟味した。　一方、日本語の不定表現とその形式意味論上の取り扱いに関しては原田を中心にして研究を進め、いくつかの項目に関して実際に文献に現れた大量の例文から問題点を抽出することに成功し、自然言語の意味論的表示における変項の取り扱いが今後の研究課題であることを認識するに至った。現在は、SRI InternationalのJ.M.Gawron博士も共同研究者に加え、日本語の不定語表現と英語の関連する構文との比較対照についてひきつづき研究を進めている。　以上の成果の一部はすでに論文やシンポジウム等で発表したが、1999年８月に開催された国際応用言語学会世界大会において本研究グループ主催によるシンポジウムを開催し、成果の集大成発表と今後の展望について討論した。