| 講演名 | 1996/11/22 系列を扱う論理型言語 関 浩之, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 系列を扱う論理型言語を定義している. 本言語におけるプログラムとは, 系列集合を定義域とする述語からなるホーン節の有限集合である. 本稿では主に, 基本的な問題の一つである論理的帰結の問題の計算量について考察する. まず, 論理的帰結の問題が一般に決定不能であることを示す. 次に, 単純生成システム (SPSと略記) と呼ばれる部分クラスを導入し, 右線形性や情報無損失性といった構文的制約をSPSプログラムに課すことによって, 論理的帰結の問題を解くために必要な計算量がどのように変化するかについて考察する. 特に, 本問題が多項式時間可解であるようなSPSの部分クラスも示す. また, 再帰なしプログラムに対する本問題の計算量についても考察する. |
| 抄録(英) | A simple logic programming language for reasoning about sequences is defined and computational complexity of the basic problems for the language is investigated. The domain of a predicate is the set of finite sequences (strings) over an alphabet with concatenation as the only interpreted operator. A program in this language is a finite set of clauses. The paper mainly investigates decidability/complexity of the logical consequence problem. First, the problem is shown to be undecidable. Then, the paper introduces a subclass of programs, called simple productive systems (SPSs for short). The paper investigates how the complexity of the problem for SPS depends on syntactical restrictions such as right-linearity and non-erasingness. |
| キーワード(和) | 論理型言語 / 演繹データベース / 計算複雑さ / 系列 |
| キーワード(英) | logic programming language / deductive database / computational complexity / sequence / string |
| 資料番号 | COMP96-44 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1996/11/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 系列を扱う論理型言語 |
| サブタイトル（和） | |
| タイトル（英） | A Logic Programming Language for Reasoning about Sequences |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 論理型言語 / logic programming language |
| キーワード(2)（和/英） | 演繹データベース / deductive database |
| キーワード(3)（和/英） | 計算複雑さ / computational complexity |
| キーワード(4)（和/英） | 系列 / sequence |
| 第 1 著者 氏名（和/英） | 関 浩之 / Hiroyuki Seki |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 発表年月日 | 1996/11/22 |
| 資料番号 | COMP96-44 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 389 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |