TERM MATCHING ON A MESH-CONNECTED ARRAY OF PROCESSORS

Authors
DELCHER AL KASIF S
Citation
Al. Delcher et S. Kasif, TERM MATCHING ON A MESH-CONNECTED ARRAY OF PROCESSORS, Annals of mathematics and artificial intelligence, 14(2-4), 1995, pp. 177-186
Citations number
14
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Artificial Intelligence
Journal title
Annals of mathematics and artificial intelligence → ACNP
ISSN journal
10122443
Volume
14
Issue
2-4
Year of publication
1995
Pages
177 - 186
Database
ISI
SICI code
1012-2443(1995)14:2-4<177:TMOAMA>2.0.ZU;2-#
Abstract
In this paper, we present a parallel algorithm for term matching of lo gical terms on a mesh-connected array of processors. Term matching is a special case of unification in which one of the terms is fully groun d, i.e. contains no variables. Term matching is a fundamental computat ional primitive in automated reasoning and has wide applicability to l ogic programming and symbolic pattern matching. Our algorithm runs in O(root N) time on a root N x root N two-dimensional mesh-connected arr ay of processors.