Affiliations: Dipartimento di Informatica, Università di Pisa,
Via Buonarroti 2, I-56127 Pisa, Italy | Dipartimento di Informatica e Scienze dell'Informazione, Università di Genova,
Via Dodecaneso 35, I-16146 Genova, Italy
Abstract: MGU_{mon} and MGU_{k-rep} have a complementary role in unification
in the complexity class NC. MGU_mon is the upper bound of the unification
classes that fall in NC and whose inputs admit an unrestricted number of
repeated variables. MGU_{k-rep} is the upper bound of the unification classes
that still fall in NC but whose inputs admit an unrestricted arity on term
constructors. No LogSpace reduction of the one to the other class is known.
Moreover, very fast algorithms that solve the two separately are well known but
no one is able to compute with both in polylog PRAM-Time. N-axioms unification
extends the structure of unification inputs and brings out the notion of interleaving variable as a special repeated variable which serializes independet computations. Based on it, we define the unification class
AMGU^k_{p/h} whose inputs have a fixed number of interleaving variables but
admit unrestricted number of repeated variables and, at the same time,
unrestricted arity for term constructors. Constructively, we prove that
AMGU^k_{p/h} is in NC by introducing a new unification algorithm that works on
graph contractions and solves AMGU^k_{p/h} in a polylog PRAM time of the
input size. Finally, we prove that MGU_{mon}, MGU_{k-rep} , and MGU_{linear}
all are LogSpace reducible to AMGU^k_{p/h}. Hence, AMGU^k_{p/h} becomes the
upper bound of the unification classes that are proved to be in NC.
