2017年
On the parameterized complexity of associative and commutative unification.
Theor. Comput. Sci.
- ,
- ,
- ,
- 巻
- 660
- 号
- 開始ページ
- 57
- 終了ページ
- 74
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.tcs.2016.11.026
- 出版者・発行元
- ELSEVIER SCIENCE BV
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. (C) 2016 The Author(s). Published by Elsevier B.V.
- リンク情報
-
- DOI
- https://doi.org/10.1016/j.tcs.2016.11.026
- DBLP
- https://dblp.uni-trier.de/rec/journals/tcs/AkutsuJTT17
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000392786200004&DestApp=WOS_CPL
- URL
- https://dblp.uni-trier.de/db/journals/tcs/tcs660.html#AkutsuJTT17
- ID情報
-
- DOI : 10.1016/j.tcs.2016.11.026
- ISSN : 0304-3975
- eISSN : 1879-2294
- DBLP ID : journals/tcs/AkutsuJTT17
- Web of Science ID : WOS:000392786200004