We show that for any ground term equation systems $E$ and $F$, (1) the union of the generated congruences by $E$ and $F$ is a congruence on the ground term algebra if and only if there exists a ground term equation system $H$ such that the congruence generated by $H$ is equal to the union of the congruences generated by $E$ and $F$ if and only if the congruence generated by the union of $E $ and $F$ is equal to the union of the congruences generated by $E $ and $F$, and (2) it is decidable in square time whether the congruence generated by the union of $E$ and $F$ is equal to the union of the congruences generated by $E $ and $F$, where the size of the input is the number of occurrences of symbols in $E$ plus the number of occurrences of symbols in $F$.
翻译:我们证明,对于任意地面项等式系统 $E$ 和 $F$,(1) 由 $E$ 和 $F$ 生成的同余的并集是地面项代数上的一个同余,当且仅当存在一个地面项等式系统 $H$,使得由 $H$ 生成的同余等于由 $E$ 和 $F$ 生成的同余的并集,当且仅当由 $E$ 和 $F$ 的并集生成的同余等于由 $E$ 和 $F$ 生成的同余的并集;并且 (2) 判定由 $E$ 和 $F$ 的并集生成的同余是否等于由 $E$ 和 $F$ 生成的同余的并集是可在平方时间内判定的,其中输入规模为 $E$ 中符号出现次数加上 $F$ 中符号出现次数。