A note on the parallel complexity of anti-unification. (English) Zbl 0784.68042

Summary: The anti-unifier is the dual notion to the unifier, i.e., it is the most specific term that has the input terms as instances. We show that the problem of anti-unification is in NC, in constrast to unification that is known to be \(P\)-complete.


68Q25 Analysis of algorithms and problem complexity
68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Bar-OnI. and VishkinU., ?Optimal parallel generation of a computation tree form?, ACM TOPLAS 7(2), 348-357 (1985). · Zbl 0564.68037 · doi:10.1145/3318.3478
[2] Cole, R., ?Parallel merge sort?, in Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 511-516 (1986).
[3] Cole, R. and Vishkin, U., ?Approximate and exact scheduling with applications to list, tree and graph problems?, in Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 478-491 (1986).
[4] DworkC., KanellakisP., and MitchellC., ?On the sequential nature of unification?, J. Logic Programming 1, 35-50 (1984). · Zbl 0588.68045 · doi:10.1016/0743-1066(84)90022-0
[5] DworkC., KanellakisP., and StockmeyerL., ?Parallel algorithms for term matching?, SIAM J. Comput. 17(4), 711-731 (1988). · Zbl 0651.68110 · doi:10.1137/0217046
[6] Fortune, S. and Wyllie, J., ?Parallelism in random access machines?, in Proc. 10th Annual ACM Symp. on Theory of Computing, ACM, pp. 114-118 (1978). · Zbl 1282.68104
[7] Huet, G., ?Resolution d’Equations dans des Languages d’Order 1, 2, ..., w?, Ph.D. thesis, Université de Paris VII (1976).
[8] MartelliA. and MontanariU., ?An efficient unification algorithm?, Trans. Programming Languages and Systems 4(2), 258-282 (1982). · Zbl 0478.68093 · doi:10.1145/357162.357169
[9] Marriott, K., Naish, L., and Lassez, J.-L., Most Specific Logic Programs, ICLP, pp. 909-923 (1988). · Zbl 0878.68036
[10] Pippenger, N., ?On simultaneous resource bounds?, in Proc. 20th Annual IEEE Symp. on Foundations of Comp. Sci., IEEE, pp. 307-311 (1979).
[11] Plotkin, G., ?A note on inductive generalization?, in Machine Intelligence 5 (eds. B. Meltzer and D. Michie), pp. 153-163 (1970). · Zbl 0219.68045
[12] PatersonM. and WegmanM., ?Linear unification?, J. Comp. System Sci. 16(2), 158-167 (1978). · Zbl 0371.68013 · doi:10.1016/0022-0000(78)90043-0
[13] Reynolds, J., ?Transformations on inductive generalization?, in Machine Intelligence 6 (eds. B. Meltzer and D. Michie), pp. 101-124 (1971).
[14] RameshR., VermaR. M., KrishnaprasadT., and RamakrishnanI. V., ?Term matching on parallel computers?, J. Logic Programming 6(3), 213-218 (1989). · Zbl 0685.68037 · doi:10.1016/0743-1066(89)90014-9
[15] Vishkin, U., ?Synchronous Parallel Computation ? A Survey?, Tech. Rep. Courant Inst., New York Univ. (1983). · Zbl 0536.68026
[16] Yasuura, H., ?On the parallel computational complexity of unification?, Tech. Rep. TR83-01, Yajima Lab. (1983).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.