Complexity of nilpotent unification and matching problems.

DOI10.1006/INCO.1999.2849MaRDI QIDQ1854363zbMATH OpenOpenAlexFDO

Authors Paliath Narendran, D. A. Wolfram, Qing Guo

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1999.2849

zbMATH Keywords

equational unification

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Unification and matching modulo nilpotence
• Complexity of unification problems with associative-commutative operators
• scientific article; zbMATH DE number 4049047
• Unification for nilpotent groups of class 2
• Matching - a special case of unification?

Cites work

• An algorithm for distributive unification
• An Efficient Unification Algorithm
• Complexity of unification problems with associative-commutative operators
• Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices
• scientific article; zbMATH DE number 4049047 (Why is no real title available?)
• scientific article; zbMATH DE number 3688776 (Why is no real title available?)
• scientific article; zbMATH DE number 108109 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 592370 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 3413831 (Why is no real title available?)
• The Clausal Theory of Types
• The complexity of satisfiability problems
• The complexity of set constraints
• The undecidability of the second-order unification problem
• Unification algorithms cannot be combined in polynomial time
• Unification in commutative theories, Hilbert's basis theorem, and Gröbner bases
• Unification in monoidal theories
• Unification in the union of disjoint equational theories: Combining decision procedures

Cited in

(6)

• Symbolic protocol analysis in the union of disjoint intruder theories: combining decision procedures
• scientific article; zbMATH DE number 4049047 (Why is no real title available?)
• Unification and matching modulo nilpotence
• scientific article; zbMATH DE number 1929957 (Why is no real title available?)
• Unification for nilpotent groups of class 2
• Complexity of unification problems with associative-commutative operators

This page was built for publication: Complexity of nilpotent unification and matching problems.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854363)