A parallel algorithm for the monadic unification problem

DOI10.1007/BF01934375MaRDI QIDQ1083189zbMATH OpenOpenAlexFDO

Authors Ivan E. Auger, Mukkai S. Krishnamoorthy

Publication date 1985

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934375

Mathematics Subject Classification ID

Classical first-order logic (03B10) Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65)

Review text

The monadic unification problem is introduced. An \(O(\log^ 2n)\) parallel algorithm to solve this problem is given and shown to be correct.

Cites work

• A Machine-Oriented Logic Based on the Resolution Principle
• A Transformation System for Developing Recursive Programs
• An Efficient Unification Algorithm
• An O(logn) parallel connectivity algorithm
• An overview of computational complexity
• Computing connected components on parallel computers
• Linear unification
• On the sequential nature of unification
• Parallelism in random access machines

Cited in

(3)

• A unification algorithm for second-order monadic terms
• On the relationship of congruence closure and unification
• Iris: monoids and invariants as an orthogonal basis for concurrent reasoning

This page was built for publication: A parallel algorithm for the monadic unification problem

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