Based on HER (hyper extension rule)

we prove that the parallelization of merging multiple EPCCL (each pair contains complementary literal) is feasible

and the corresponding algorithm PUAE (parallel computing union of any number of EPCCL) is proposed. Through using the origin CNF formulae of EPCCL theories

another efficient merging algorithm imp-PUAE (improvement of PUAE) is proposed. UKCHER (computing union sets of maximum terms for knowledge compilation based on hyper extension rule) is a knowledge compilation algorithm for EPCCL

which can be parallelized. Based on the above methods

we proposed two parallel knowledge compilation algorithms i. e.

P-UKCHER (UKCHER with PUAE) and impP-UKCHER (UKCHER with imp-PUAE)

which use the PUAE algorithm and imp-PUAE algorithm

respectively. Experimentally

although P-UKCHER does not improve the efficiency of UKCHER

the compilation quality is improved. In the best case

the compilation quality can be improved by 4 times with P-UKCHER. The impP-UKCHER can improve the efficiency and compilation quality of UKCHER at the same time

and the compilation quality can also be improved by 4 times in the best case.