ダウンロード数: 196
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.tcs.2016.11.026.pdf | 571.03 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Akutsu, Tatsuya | en |
dc.contributor.author | Jansson, Jesper | en |
dc.contributor.author | Takasu, Atsuhiro | en |
dc.contributor.author | Tamura, Takeyuki | en |
dc.contributor.alternative | 阿久津, 達也 | ja |
dc.contributor.alternative | 田村, 武幸 | ja |
dc.date.accessioned | 2018-11-12T05:41:43Z | - |
dc.date.available | 2018-11-12T05:41:43Z | - |
dc.date.issued | 2017-01-17 | - |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | http://hdl.handle.net/2433/235021 | - |
dc.description.abstract | This article studies the parameterized complexity of the unification problem with associative, commutative, or associative-commutative functions with respect to the parameter “number of variables”. It is shown that if every variable occurs only once then both of the associative and associative-commutative unification problems can be solved in polynomial time, but that in the general case, both problems are W[1]-hard even when one of the two input terms is variable-free. For commutative unification, an algorithm whose time complexity depends exponentially on the number of variables is presented; moreover, if a certain conjecture is true then the special case where one input term is variable-free belongs to FPT. Some related results are also derived for a natural generalization of the classic string and tree edit distance problems that allows variables. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Elsevier BV | en |
dc.rights | © 2016 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). | en |
dc.subject | Unification | en |
dc.subject | Parameterized algorithm | en |
dc.subject | Dynamic programming | en |
dc.subject | Tree edit distance | en |
dc.title | On the parameterized complexity of associative and commutative unification | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | Theoretical Computer Science | en |
dc.identifier.volume | 660 | - |
dc.identifier.spage | 57 | - |
dc.identifier.epage | 74 | - |
dc.relation.doi | 10.1016/j.tcs.2016.11.026 | - |
dc.textversion | publisher | - |
dc.address | Bioinformatics Center, Institute for Chemical Research, Kyoto University | en |
dc.address | Bioinformatics Center, Institute for Chemical Research, Kyoto University | en |
dc.address | National Institute of Informatics, Tokyo | en |
dc.address | Bioinformatics Center, Institute for Chemical Research, Kyoto University | en |
dcterms.accessRights | open access | - |
datacite.awardNumber | 26240034 | - |
datacite.awardNumber | 25730005 | - |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName.alternative | Japan Society for the Promotion of Science (JSPS) | en |
jpcoar.funderName.alternative | Japan Society for the Promotion of Science (JSPS) | en |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。