WEKO3
アイテム
Tractable and intractable second-order matching problems
http://hdl.handle.net/10228/374
http://hdl.handle.net/10228/374c651c5cd-c4dc-44b0-b614-16fe40ad8070
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
j.jsc.2003.09.002.pdf (195.0 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2007-11-20 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Tractable and intractable second-order matching problems | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
平田, 耕一
× 平田, 耕一
WEKO
597
× Yamada, Keizo× Harao, Masateru |
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | The second-order matching problem is to determine whether or not afirst-order term without variables is an instance of a second-order termthat is allowed to contain not only individual variables but also functionvariables. It is well-known that the second-order matching problemis NP-complete in general. In this paper, we first introduce the severalrestrictions for the second-order matching problems, such as the boundednumber, arity and occurrence of function variables, ground that containsno individual variables, flat that contains no function constants, and predicatethat no function variable occurs in the terms of arguments of eachfunction variable. By combining the above restrictions, we give the sharpseparations of tractable second-order matching problems from intractableones. Finally, we compare them with the separations of decidable secondorderunification problems from undecidable ones. | |||||||||||||
| 言語 | en | |||||||||||||
| 書誌情報 |
en : Journal of Symbolic Computation 巻 37, 号 5, p. 611-628, 発行日 2004-05 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | Elsevier | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.jsc.2003.09.002 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0747-7171 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||
| 収録物識別子 | 1095-855X | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2003 Elsevier Ltd. | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Second-order matching problem | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Second-order unification problem | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Computational complexity | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | AM | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
