非線形TRSのE重なり性について
スポンサーリンク
概要
- 論文の詳細を見る
項書換えシステム(TRS)の重要な性質の一つに合流性があり, 最近, 非線形TRSにおいては非E重なり性がその合流性と密接に関係していることが報告された. しかし, 非E重なり性は一般に非可解な問題である. 本論文では, まず「深さ保存」の概念を導入し, TRSが深さ保存的であるとき, 非ω重なりならば非E重なりであることを示す. 非ω重なり性は判定可能な性質であることから, この結果を用いて, 合流性を保証する判定可能な十分条件をいくつか導くことができることを示す. 次に, 右定項TRSのクラスに限定すれば非E重なり性判定間題が可解であることを明らかにする.
- 社団法人電子情報通信学会の論文
- 1997-11-25
著者
-
大山口 通夫
三重大学工学研究科
-
太田 義勝
Faculty Of Engineering Mie University
-
太田 義勝
三重大学工学部
-
小川 瑞史
北陸先端科学技術大学院大学
-
小川 瑞史
Ntt基礎研究所
-
小川 瑞史
Ntt
-
松浦 邦博
三重大学工学部情報工学科
-
松浦 邦博
三重大
-
小川 瑞史
Ntt ソフトウェア研究所
-
大山口 通夫
三重大学大学院工学研究科情報工学専攻
関連論文
- 文脈を考慮したJavaプログラムの参照先解析に関する一考察 (アルゴリズムと計算機科学の数理的基盤とその応用)
- モデル検査技術を利用したプログラム解析器の生成ツール
- ソフトウェア科学会第4回大会
- イベント順序証明システムの正当性の形式的証明
- 抽象実行 そのフレームワークと実例(その3)
- 抽象実行 そのフレームワークと実例(その2)
- 抽象解釈におけるLazyな抽象領域の生成
- 抽象実行 そのフレームワークと実例(その1)
- 最小不動点計算に基づくプログラムの帰納的性質の導出 (並列処理)
- 広域データフロー解析に基づく関数型プログラムの変則性検出
- さきがけ「機能と構成」研究1 : 効率的で正しいプログラムの自動生成
- ASIA-PEPM 2002/FLOPS 2002参加報告
- 利得の最適連想規則を求める線形時間アルゴリズムの導出
- 最大重み和問題の線形時間アルゴリズムの導出
- ACM PLI 2000会議報告
- ナップサック問題およびその発展問題の統一的解法
- ルートE重なりな深さ保存項書き換えシステムのチャーチ・ロッサー性について
- ルートE重なりな深さ保存項書き換えシステムのチャーチ・ロッサー性について
- On the Church-Rosser Property of Non-E-overlapping and Weight-Preserving TRS's
- 再帰手続きに対する新しいコード最適化
- 非線形TRSのE重なり性について
- 書換え系のPerpetual性と一様停止性
- 高階書換え系の単一正規形性
- 逐次性v.s.ストリクト性 : 非線形項書換え系の最適戦略にむけて
- 高階書き換え系の単一正規形性
- 項グラフ書換え系における単純ギャップ停止性
- 91-37 パラメトリシティの証明論の概略
- 理論計算機科学に関する豊橋シンポジウムに参加して
- 単純型付き等式系に基づく定理自動証明に関する一考察(計算機科学の理論とその応用)
- グラフマイナー定理に基づく線形時間アルゴリズムの自動生成
- 非線形項書き換えシステムのE-非オーバーラップ性について(理論計算機科学とその周辺)
- プロセス間通信に基づく並列処理言語の表示的意味記述について
- 非同期通信に基づく並列処理言語の表示的意味記述について(計算アルゴリズムと計算量の基礎理論)
- A-011 An Extension of E-overlapping Notion in Term Rewriting Systems and its Applications
- 非線形TRSのE重なり性判定問題について(計算量理論)
- 89-29 ストリクトネス解析に基づく関数型プログラムの計算量解析
- 87-21 関数型プログラムの静的解析
- A-017 厳密解法と発見的手法の組合せによるサイズ可変ビンパッキング問題の解法(モデル・アルゴリズム・プログラミング,一般論文)
- The Joinability and Related Decision Problems for Semi-constructor TRSs(計算理論)
- The Confluence Problem for Flat TRSs(New Trends in Theory of Computation and Algorithm)
- The Reachability and Related Decision Problems for Semi-Constructor TRSs (Theoretical Computer Science and its Applications)
- The Joinability and Unification Problems for Confluent Semi-Constructor TRSs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- 単項的TRSにおける単ー化問題について
- 並列処理を考慮した目的コードスケジューリング
- A-016 DAGの高さを4以下に制限したタスクスケジューリングの近似アルゴリズムについて(A分野:モデル・アルゴリズム・プログラミング)
- 通信遅延を考慮したタスクスケジューリングアルゴリズムについて(研究速報)
- 最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論とその応用)
- 最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論の新展開)
- グリッドコンピューティングにおける代理証明書信任リスト(ディペンダブルソフトウェア)
- 巡回セールスマン問題の近似アルゴリズムについて
- 3大プロセッサスケジューリングに関する一考察
- 単純右線形項書換えシステムの合流性について
- E重なりのある単純右線形項書き換えシステムの合流性について
- 「情報処理学会論文誌 : プログラミング」の編集について
- D-3-4 教育用C言語とそのコンパイラに関する一考察(D-3.ソフトウェアサイエンス,一般講演)
- On the Church-Rosser Property of Non-E-overlapping and Strongly Depth-preserving Term Rewriting Systems
- DAG の高さを4以下に制限したタスクスケジューリングの近似アルゴリズムについて(計算機科学の理論とその応用)
- タスクスケジューリングに関する新しい近似アルゴリズムについて (計算機科学基礎理論の新展開)
- マルチプロセッサ向き目的コードスケジューリングについて
- レベル付き依存グラフを用いた効率のよいソフトウェア・パイプライン化法について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- マルチプロセッサ向き目的コードスケジューリングについて
- 構文解析法からみた最近の計算機言語理論の動向
- マルチプロセッサ向き目的コードスケジューリングについて
- マルチプロセッサ向き目的コードスケジューリングについて (アルゴリズムと計算の理論)
- 弱単項TRSのE重なり性について
- Shibboleth・CAS連携による東海アカデミッククラウド認証基盤の構築(学生セッション,一般)
- 「情報処理学会論文誌 : プログラミング」の編集について
- 左線形項書換えシステムのチャーチ・ロッサー性に対する新しいParallel Closed条件
- Proxy Certificate Trust List for Grid Computing
- レジスタ割り当てにおける循環区間グラフの彩色アルゴリズムについて
- 右定項-項書換えシステムの合流性について
- 分散オペレーティング・システムISEとその並列処理言語について