TY - GEN
T1 - New algorithms for unification modulo one-sided distributivity and its variants
AU - Marshall, Andrew M.
AU - Narendran, Paliath
PY - 2012
Y1 - 2012
N2 - An algorithm for unification modulo one-sided distributivity is an early result by Tiden and Arnborg [14]. Unfortunately the algorithm presented in the paper, although correct, has recently been shown not to be polynomial time bounded as claimed [11]. In addition, for some instances, there exist most general unifiers that are exponentially large with respect to the input size. In this paper we first present a new polynomial time algorithm that solves the decision problem for a non-trivial subcase, based on a typed theory, of unification modulo one-sided distributivity. Next we present a new polynomial algorithm that solves the decision problem for unification modulo one-sided distributivity. A construction, employing string compression, is used to achieve the polynomial bound.
AB - An algorithm for unification modulo one-sided distributivity is an early result by Tiden and Arnborg [14]. Unfortunately the algorithm presented in the paper, although correct, has recently been shown not to be polynomial time bounded as claimed [11]. In addition, for some instances, there exist most general unifiers that are exponentially large with respect to the input size. In this paper we first present a new polynomial time algorithm that solves the decision problem for a non-trivial subcase, based on a typed theory, of unification modulo one-sided distributivity. Next we present a new polynomial algorithm that solves the decision problem for unification modulo one-sided distributivity. A construction, employing string compression, is used to achieve the polynomial bound.
UR - https://www.scopus.com/pages/publications/84863616989
U2 - 10.1007/978-3-642-31365-3_32
DO - 10.1007/978-3-642-31365-3_32
M3 - Conference contribution
SN - 9783642313646
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 408
EP - 422
BT - Automated Reasoning - 6th International Joint Conference, IJCAR 2012, Proceedings
T2 - 6th International Joint Conference on Automated Reasoning, IJCAR 2012
Y2 - 26 June 2012 through 29 June 2012
ER -