Decomposable Termination of Composable Term Rewriting Systems
スポンサーリンク
概要
- 論文の詳細を見る
We extend the theorem of Gramlich on modular termination of term rewriting systems, by relaxing the disjointness condition and introducing the composability instead. More precisely, we prove that if R_l, R_<-1> are composable, terminating term rewriting systems such that their union is nonterminating then for some a ∈ {1, -1}, R_a ∪ OR is nonterminating and R_<-a>\Ra is Fa-lifting. Here, OR is defined to be the special system {or(x, y) → x, or(x, y) → y}, Fa is the set of function symbols associated with Ra, and an Fa -lifting system contains a rule which has either a variable or a symbol from Fa at the leftmost position of its right-hand side. The extended theorem is stronger than the original one in that it relaxed the disjointness and constructor-sharing conditions and allowed the two systems to share defined symbols in common under the restriction of composability. The corollaries of the theorem show several sufficient conditions for decomposability of termination, which are useful for proving termination of term rewriting systems defined by combination of several composable modules.
- 社団法人電子情報通信学会の論文
- 1995-04-25
著者
-
Ohuchi Azuma
Faculty Of Engineering Hokkaido University
-
KURIHARA Masahito
Faculty of Engineering, Hokkaido University
-
Kurihara Masahito
Faculty Of Engineering Hokkaido University
関連論文
- 4R-3 リンク構造を考慮したベクトル空間法によるWebグラフ分割の実験的解析(Webマイニング,学生セッション,データベースとメディア)
- 対立の弁証法的解決に向けた妥協的推論の形式化
- 動的ファジィ制約充足における解の安定性維持
- 2Q-5 Java PathFinderによるモデル検査におけるGUIの提案(検査,検証,解析,学生セッション,ソフトウェア科学・工学)
- マッピング手法の導入によるインタラクション・モデルの拡張
- セマンティック・ウェブ技術を応用したユーザ嗜好インタフェースの実現
- 1R-2 可変スニペットとキーワード相関グラフを利用した検索補助インタフェースの提案(Web検索支援,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 3V-8 シソーラス利用による童話文からの感情情報読み取りシステム(文章・感情,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 主観的メタ情報を利用した顔画像に対する個人嗜好推定の研究
- 4T-7 動的スクリプトにおけるルールの内部情報を考慮した多様性の向上(ゲーム,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 1W-1 太陽電池の特性を自動学習する高速な最大電力点追従装置の開発と実装(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 適応型合意形成モデルにおけるエージェントの特性分析
- 連続離散混合領域におけるファジィ制約充足問題とその反復改善型解法
- 1次元空間における固定半径ランダムグラフの連結性の理論解析
- 1次元空間における固定半径ランダムグラフの連結性の理論解析(アルゴリズム一般)
- 2ZC-5 アプリケーション層マルチキャストにおけるアーカイブ取得方式の提案とその応用(P2P,学生セッション,ネットワーク,情報処理学会創立50周年記念)
- 1Y-6 複数の顔器官イラストの組み合わせによる顔イラストの作成支援システム(画像生成,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 5W-4 実体験情報を含むBlogを抽出するシステム(言語情報抽出,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 6U-3 話者適応手法を用いた合成音声の個性化(音声・歌声合成,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 5P-4 キーワードプログラミングの改良と実装(プログラミング環境・教育,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- Constraint-Based Multi-Completion Procedures for Term Rewriting Systems
- 系統的/局所的探索の協調によるファジィ制約充足問題の近似解法
- サービス・ロジックとインタフェースの分離によるユーザ嗜好モダリティの実現
- ランダム区間グラフによる1次元アドホックネットワークの連結性のモデル化とその閉じた解
- 1N-7 分散システムの状態変化に対する非集中化モニタリング手法の提案(システム評価,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 6L-2 Windowsにおける大規模分散システムテストベッドの開発(仮想化技術(2),学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 依存対法を用いた項書換え系多重完備化手続き
- 項書換え系多重完備化手続きにおける新たな半順序制約表現の導入
- ステータス付き再帰的経路順序による項書換え系多重完備化手続きの実装と性能評価(計算モデル,フォーマルアプローチ論文)
- F-052 単語の重要度と頻度を利用した局所探索に基づくWEBページ発見法(人工知能・ゲーム,一般論文)
- 感性語の階層構造を利用した配色における個性の抽出と活用
- 障害物密度に応じた迷路探索問題の難易度指標と実時間探索アルゴリズムの性能解析
- 1次元固定半径ランダムグラフの連結性に対する閉じた解(セッション4)
- 多重パスメッセージ転送ネットワークの数理モデルと論理
- 優先順位と二分決定グラフに基づく複数経路順序下の項書換え系完備化手続き
- プログラムの変更履歴に基づくリファクタリング支援
- Implementation of Conditional Term Rewriting Systems equipped with Meta-computation(Theory of Rewriting Systems and Its Applications)
- Modular Term Rewriting Systems with Shared Constructors
- Decomposable Termination of Composable Term Rewriting Systems
- 情報教養教育の新展開 : 情報教養教育研究会報告書
- Another Representation of Integers in Logic
- Another Representation of Integers in Logic
- Supporting Refactoring Activities Using Histories of Program Modification(Knowledge-Based Software Engineering)
- Another Representation of Integers in Logic
- 大学への秋入学について
- 例題で学ぶJava入門, 大堀隆文, 木下正博(共著), コロナ社(2012-11), A5判, 定価(本体2,200円+税)