ダウンロード数: 195
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.tcs.2016.11.026.pdf | 571.03 kB | Adobe PDF | 見る/開く |
タイトル: | On the parameterized complexity of associative and commutative unification |
著者: | Akutsu, Tatsuya https://orcid.org/0000-0001-9763-797X (unconfirmed) Jansson, Jesper Takasu, Atsuhiro Tamura, Takeyuki https://orcid.org/0000-0003-1596-901X (unconfirmed) |
著者名の別形: | 阿久津, 達也 田村, 武幸 |
キーワード: | Unification Parameterized algorithm Dynamic programming Tree edit distance |
発行日: | 17-Jan-2017 |
出版者: | Elsevier BV |
誌名: | Theoretical Computer Science |
巻: | 660 |
開始ページ: | 57 |
終了ページ: | 74 |
抄録: | 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. |
著作権等: | © 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/). |
URI: | http://hdl.handle.net/2433/235021 |
DOI(出版社版): | 10.1016/j.tcs.2016.11.026 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。