Skip navigation
Skip navigation

Complexity of Nilpotent Unification and Matching Problems

Guo, Qing; Narendran, Paliath; Wolfram, David

Description

We consider the complexity of equational unification and matching problems where the equational theory contains a nilpotent function, i.e., a function f satisfying f(x, x) = 0 where 0 is a constant. We show that nilpotent unification and matching are NP-complete. In the presence of associativity and commutativity, the problems still remain NP-complete. However, when 0 is also assumed to be the unity for the function f, the problems are solvable in polynomial time. We also show that the problem...[Show more]

CollectionsANU Research Publications
Date published: 2000
Type: Journal article
URI: http://hdl.handle.net/1885/89088
Source: Information and Computation
DOI: 10.1006/inco.1999.2849

Download

File Description SizeFormat Image
01_Guo_Complexity_of_Nilpotent_2000.pdf169.67 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator