シーラ・グライバッハ

シーラ・アデル・グライバッハ（1939年10月6日ニューヨーク生まれ）は、コンピューターにおける形式言語、オートマトン、コンパイラ理論、コンピューターサイエンスのアメリカ人研究者である。カリフォルニア大学ロサンゼルス校のコンピューターサイエンスの名誉教授であり、シーモア・ギンズバーグやマイケル・A・ハリソンと共同でスタックオートマトンモデルを使用した文脈依存構文解析に取り組んだことが著名な研究である。

1965年に文脈自由文法の正規形（グライバッハ正規形）を確立したほか、 W文法、プッシュダウンオートマトン、決定可能性問題などの特性も研究した。

グライバッハは1960年にラドクリフ大学で言語学と応用数学の学士号（最優秀）を取得し、その2年後に文学修士号を取得した。1963年に彼女はハーバード大学で博士号を授与され、アンソニー・エッティンガー^[1]の指導の下、 「句構造生成器の逆」と題する博士論文を執筆した。

彼女はハーバード大学の工学・応用物理学部門で1969年まで勤務し、その後UCLAに移り、現在（2014年3月現在）まで教授を務めています。

彼女の教え子には、ロナルド・V・ブックやマイケル・J・フィッシャーがいた。次のリストは彼女の作品の一部を示したものである。リストの上の部分は ACM デジタルライブラリから、残りの部分はデビッド・M・ジョーンズ著の FOCS 書誌から引用した。

「ジャンプ PDA、決定論的文脈自由言語、主要な AFDL、多項式時間認識 (拡張要約)」、第 5 回 ACM コンピューティング理論シンポジウムの議事録、1973 年 4 月

すべての決定論的文脈自由言語は、ジャンプを伴う決定論的有限遅延PDAによって受け入れられます。ジャンプの種類または発生回数が増えると、有限遅延で受け入れられる言語のファミリが増加します。したがって、決定論的文脈自由言語のファミリは主要な AFDL です。すべての文脈自由言語がまたはの逆 GSM イメージであるような文脈自由言語が存在します。${\displaystyle L_{0}}$${\displaystyle L_{0}}$${\displaystyle L_{0}-\{e\}}$

「W 文法に関するいくつかの制限」第 6 回 ACM コンピューティング理論シンポジウム議事録、1974 年 4 月

W 文法( ALGOL 68の構文の形式化)に対するいくつかの制限の影響について検討します。詳細に検討した 2 つの比較できないファミリは、WRB (通常の正規ベースの W 文法によって生成された言語) と WS (単純な W 文法によって生成された言語) です。どちらもコンテキスト フリー言語を適切に含み、準リアルタイム言語のファミリに適切に含まれています。さらに、WRB はネストされた反復処理の下で閉じています...

「文脈自由言語の無限階層」、Journal of the ACM、 第 16 巻第 1 号、1969 年 1 月

「文脈自由句構造文法のための新しい正規形定理」、JACM、 第 12 巻第 1 号、1965 年 1 月

「線形文脈自由言語の認識の不可能性」、JACM、 第 13 巻第 4 号、1966 年 10 月

与えられた文脈自由言語が線形であるかどうかという問題は、再帰的に決定不可能であることが示されています。

「マルチテープ AFA」、シーモア・ギンズバーグとの共著、Journal of the ACM、第 19 巻第 2 号、1972 年 4 月

「超決定論的 PDA: 決定可能な包含問題を伴うサブケース」、EP Friedman との共著、「JACM」、1980 年 10 月、第 27 巻第 4 号

「スタックオートマトンとコンパイル」、シーモア・ギンズバーグ、マイケル・A・ハリソンとの共著、「JACM」、1967年1月、第14巻第1号

コンパイルは、認識と変換の 2 つの部分から構成されます。多くの最新のコンパイル技術の顕著な特徴を具体化した数学モデルが提示されます。スタック オートマトンと呼ばれるこのモデルは、本質的に決定論的であるという望ましい特徴を備えています。この決定論的デバイスは、非決定論的デバイス (非決定論的スタック オートマトン) に一般化され、このより一般的なデバイスの特定のインスタンスが示されています。非決定論的スタック オートマトンによって受け入れられるセットは再帰的です...

「準リアルタイム言語 (拡張要約)」、ロナルド V. ブックとの共著、第 1 回 ACM コンピューティング理論シンポジウム議事録、1969 年 5 月

準リアルタイム言語は、非決定性マルチテープチューリング マシンによってリアルタイムで受け入れられる言語です。準リアルタイム言語のファミリは、交差、線形消去、および反転に対して閉じた抽象的な言語ファミリを形成します。これは、非決定性マルチテープ チューリング マシンによって線形時間で受け入れられる言語ファミリと同一です。すべての準リアルタイム言語は、非決定性 1 スタック、1 プッシュダウン ストア マシンによってリアルタイムで受け入れられ、e ...

「一方向スタックオートマトン」、シーモア・ギンズバーグ、マイケル・A・ハリソンとの共著、「JACM」、1967年4月、第14巻第2号

一方向スタックオートマトンによって受け入れられるセットを保存するか、決定論的一方向スタックオートマトンによって受け入れられるセットを保存するいくつかの操作が提示されています。たとえば、シーケンシャルトランスダクションは前者を保存し、セット補完は後者を保存します。いくつかの解決可能性の問題も考慮されます。

「テープおよび時間制限付きチューリング アクセプタと AFL (拡張要約)」、Ronald V. Book および Ben Wegbreit との共著、第 2 回 ACM コンピューティング理論シンポジウムの議事録、1970 年 5 月

時間制限およびテープ制限のチューリング アクセプタによって定義される形式言語の複雑性クラスを研究し、これらのクラスが AFL および主 AFL となるための十分な条件を示します。

「均一に消去可能な AFL」、シーモア・ギンズバーグおよびジョナサン・ゴールドスタインとの共著、第 4 回 ACM コンピューティング理論シンポジウム議事録、1972 年 5 月

この論文では、よく知られているファミリーの多くが特性 (*) を持っていることを示した。特に、著者らは文脈自由言語のファミリーが実際にこの特性を持っていることを証明した。さらに、1 カウンタ言語などの文脈自由言語のいくつかのよく知られたサブファミリーが特性 (*) を持っていることを示す。最後に、文脈自由言語のサブファミリーではない (*) を満たすファミリーが存在することを示す。なぜなら、1 文字から生成されるファミリーはどれも特性 (*) を持っていることを証明しているからである... ^{[明確化が必要]}

形式構文解析システム

シーラ・A・グライバッハ

1964年8月

ACM 通信、第 7 巻第 8 号

自動構文解析は、最近、自然言語データ処理と構文指向コンパイラの両方にとって重要になっています。形式解析システム G = (V, μ, T, R) は、2 つの有限の互いに素な語彙 V と T、V から T への多対多マップ μ、および構文文クラスと呼ばれる T 内の文字列の再帰セット R で構成されます...

シーモア・ギンズバーグとシーラ・グライバッハ。

決定論的文脈自由言語。

第 6 回スイッチング回路理論および論理設計シンポジウム議事録、203-220 ページ。IEEE、1965 年。

シーモア・ギンズバーグ、シーラ・A・グライバッハ、マイケル・A・ハリソン。

一方向スタックオートマトン（拡張抽象）。

1966 年第 7 回スイッチングおよびオートマトン理論シンポジウムの会議記録、47-52 ページ、カリフォルニア州バークレー、1966 年 10 月 26 日～28 日。IEEE。

シーラ・A・グライバッハ。

文脈自由言語の無限階層。

1967 年第 8 回スイッチングおよびオートマトン理論シンポジウムの会議記録、32-36 ページ、テキサス州オースティン、1967 年 10 月 18 ～ 20 日。IEEE。

シーモア・ギンズバーグとシーラ・グライバッハ。

言語の抽象的なファミリー。

1967 年第 8 回スイッチングおよびオートマトン理論シンポジウムの会議記録、128 ～ 139 ページ、テキサス州オースティン、1967 年 10 月 18 ～ 20 日。IEEE。引用。

シーラ・グライバッハ。

オートマトンと一方向スタック言語のチェック (拡張概要)。

1968 年第 9 回スイッチングおよびオートマトン理論シンポジウムの会議記録、287-291 ページ、ニューヨーク州スケネクタディ、1968 年 10 月 15 ～ 18 日。IEEE。引用。

シーラ・A・グライバッハ。

完全な AFL とネストされた反復置換。

1969 年第 10 回スイッチングおよびオートマトン理論シンポジウムの会議記録、222-230 ページ、カナダ、オンタリオ州ウォータールー、1969 年 10 月 15 ～ 17 日。IEEE。

JW カーライル、SA グレイバッハ、A. パズ。

二元細胞分裂による成長をモデル化した二次元生成システム（予備報告）。

第 15 回スイッチングおよびオートマトン理論シンポジウム、1-12 ページ、ニューオーリンズ大学、1974 年 10 月 14 ～ 16 日。IEEE。

SAグライバッハ。

形式言語：起源と方向性。

第 20 回コンピュータサイエンスの基礎に関する年次シンポジウム、66-90 ページ、プエルトリコ、サンファン、1979 年 10 月 29 ～ 31 日。IEEE。

ロナルド・ブック、シモン・エヴェン、シーラ・グライバッハ、ジーン・オット。

グラフと表現の曖昧さ。

IEEE Transactions on Computers、vol. c-20、No. 2、1971 年 2 月。IEEE。

• グライバッハ正規形
• アクセプタの抽象ファミリー
• グライバッハの定理

• シーラ・グレイバッハのUCLA教員ページ