%%Page: 1 1 1 0 bop 7731 11608 a Fy(Na)-38 b(vig)-10 b(ating)480 b(through)g(Object)f(Graphs)g(Using)g(Local)19050 14043 y(Meta-Information)16513 17802 y Fx(Karl)332 b(Lieberherr)h(and)f (Mitchell)h(W)-106 b(and)35293 17320 y Fw(\003)18073 20902 y Fx(Colle)-20 b(ge)333 b(of)f(Computer)i(Science)19529 22452 y(Northeastern)f(Uni)-33 b(v)-20 b(ersity)17291 24001 y(360)333 b(Huntington)h(A)-98 b(v)-20 b(enue,)332 b(161CN)19132 25551 y(Boston,)g(MA)g(02115,)h(USA)15206 27101 y(w)-13 b(and@ccs.neu.edu,)333 b(lieber@ccs.neu.edu)13897 28651 y(http://www)-86 b(.ccs.neu.edu/home/)p Fu(f)p Fx(lieber)-53 b(,)335 b(w)-13 b(and)p Fu(g)20629 31736 y Fx(No)-20 b(v)g(ember)333 b(23,)f(2004)5978 38517 y Ft(Abstract)5978 40686 y Fs(T)-42 b(ra)-24 b(v)-18 b(ersal)317 b(through)j(object)g(graphs)g(is)f(needed)h(for)g(man)-18 b(y)320 b(programming)f(tasks.)425 b(W)-97 b(e)321 b(sho)-30 b(w)5978 42192 y(ho)g(w)464 b(this)g(task)g(may)h(be)g(speci\002ed)f (declarati)-30 b(v)-18 b(ely)465 b(at)f(a)h(high)g(le)-30 b(v)-18 b(el)464 b(of)g(abstraction,)505 b(and)5978 43697 y(we)335 b(gi)-30 b(v)-18 b(e)335 b(a)h(simple)f(and)g(intuiti)-30 b(v)-18 b(e)335 b(semantics)g(for)f(such)h(speci\002cations.)472 b(The)336 b(algorithm)f(is)5978 45203 y(implemented)303 b(in)g(a)g(Ja)-24 b(v)-30 b(a)303 b(library)f(called)i(DJ.)5978 49023 y Ft(1)1328 b(Intr)-24 b(oduction)5978 51192 y Fs(A)313 b(common)g(task)f(in)h(object-oriented)g(programming)g(is)f (to)h(tak)-12 b(e)313 b(an)g(object)g Fq(o)g Fs(in)g(an)g(object)5978 52698 y(graph)276 b(and)g(\002nd)g(all)g(the)h(objects)f Fq(o)20764 52258 y Fo(0)21339 52698 y Fs(that)g(are)g(reachable)h(from) e Fq(o)h Fs(according)g(to)h(some)e(search)5978 54203 y(criterion.)675 b(F)-18 b(or)402 b(e)-18 b(xample,)429 b(gi)-30 b(v)-18 b(en)402 b(an)i(object)f Fq(o)g Fs(of)g(class)f Fl(A)p Fs(,)h(\002nd)g(all)g(the)g(objects)g(of)g(class)5978 55709 y Fl(C)419 b Fs(that)h(are)g(reachable)g(from)f Fq(o)g Fs(along)h(a)g(path)g(that)f(goes)h(through)f(some)h(object)g (of)f(class)5978 57214 y Fl(B)p Fs(.)344 b(In)g(order)f(to)h(mak)-12 b(e)345 b(the)f(search)g(tractable,)354 b(we)345 b(typically)f(search)g (based)g(on)g Fq(local)g(meta-)5978 58720 y(information)p Fs(.)364 b(In)269 b(such)h(a)f(search,)276 b(we)270 b(search)g(only)f (those)h(edges)f(from)g Fq(o)h Fs(that)g Fq(might)291 b Fs(lead)270 b(to)5978 60225 y(an)256 b(object)h(that)f(satis\002es)f (the)h(search)g(criterion,)266 b(based)256 b(on)g(the)h(class)e (structure)g(of)h(the)h(object)5978 61731 y(graph.)353 b(W)-97 b(e)238 b(may)g(e)-18 b(xplore)237 b(objects)g(that)g(are)h (not)f(on)g(the)h(path)f(to)h(a)f(desired)g(tar)-22 b(get)237 b(object,)251 b(b)-24 b(ut)5978 63236 y(that)303 b(is)f(an)i(una)-24 b(v)g(oidable)303 b(consequence)h(of)e(searching)h(based)g(only)g(on)g (meta-information.)p 5978 63993 15940 45 v 7328 64772 a Fk(\003)7771 65134 y Fv(W)-80 b(ork)551 b(supported)g(by)g(the)g (National)h(Science)g(F)-15 b(oundation)552 b(under)f(grants)g (CCR-9804115,)625 b(CCR-)5978 66351 y(0097740,)250 b(and)f (CCR-0098643,)g(and)g(by)h(ARP)-92 b(A)249 b(and)h(BBN)e(under)i (agreement)g(F33615-00-C-1694.)25600 69672 y Fs(1)p eop %%Page: 2 2 2 1 bop 7859 7638 a Fs(In)286 b(this)f(paper)h(we)g(present)g(a)g (simple)f(semantics)h(for)f(such)h(a)g(search,)j(and)d(introduce)g(an) 5978 9143 y(algorithm)398 b(for)g(performing)g(the)g(search,)422 b(gi)-30 b(v)-18 b(en)399 b(a)g(search)f(criterion)g(lik)-12 b(e)398 b(the)h(one)g(abo)-18 b(v)g(e.)5978 10649 y(The)344 b(semantics)h(and)g(algorithm)g(address)f(tw)-12 b(o)345 b(technical)h(problems:)459 b(the)345 b(meaning)g(of)g(the)5978 12154 y(modal)337 b(operator)g(\223might\224,)347 b(and)338 b(the)f(treatment)h(of)f(inheritance.)479 b(W)-97 b(e)338 b(gi)-30 b(v)-18 b(e)337 b(an)h(e)-18 b(xample)337 b(of)5978 13660 y(this)302 b(algorithm)h(as)g(embodied)g(in)g(the)h(DJ)e(library) h(for)f(Ja)-24 b(v)-30 b(a)302 b([1].)7859 15557 y(Section)421 b(2)g(presents)f(our)h(notation,)450 b(and)421 b(section)g(3)f (presents)g(our)h(model)g(of)f(classes)5978 17062 y(and)409 b(objects.)692 b(In)409 b(section)g(4,)435 b(we)409 b(formulate)f(the)h (basic)g(tra)-24 b(v)-18 b(ersal)407 b(problem)i(in)g(the)g(terms)5978 18568 y(of)375 b(our)g(model.)593 b(The)375 b(k)-12 b(e)-18 b(y)375 b(to)g(the)h(problem)f(is)g(to)g(\002nd)h(a)f(set)g(FIRST)p Fi(\()p Fq(c)p Fp(;)135 b Fq(c)37944 18128 y Fo(0)38240 18568 y Fi(\))375 b Fs(of)g(edges)g(such)5978 20073 y(that)334 b Fq(e)287 b Fh(2)f Fs(FIRST)p Fi(\()p Fq(c)p Fp(;)135 b Fq(c)15369 19633 y Fo(0)15666 20073 y Fi(\))333 b Fs(if)-30 b(f)333 b(it)i(is)e(possible)h(for)g(an)g(object)h(of)f(class)g Fq(c)g Fs(to)h(reach)f(an)h(object)f(of)5978 21579 y(type)351 b Fq(c)8954 21139 y Fo(0)9604 21579 y Fs(by)g(a)g(path)h(be)-18 b(ginning)351 b(with)g(an)h(edge)f Fq(e)p Fs(.)520 b(Section)352 b(5)f(gi)-30 b(v)-18 b(es)350 b(semantics)h(to)g(the)g(core)5978 23084 y(tra)-24 b(v)-18 b(ersal)239 b(speci\002cations)i(of)f(DJ)h(and) g(sho)-30 b(ws)240 b(ho)-30 b(w)240 b(to)h(interpret)g(them)g(as)f (search)h(algorithms.)5978 24590 y(Section)f(6)g(completes)h(the)f (story)f(by)i(sho)-30 b(wing)239 b(ho)-30 b(w)241 b(to)f(compute)h(the) f(FIRST)g(sets)f(statically)-79 b(.)5978 26095 y(Section)405 b(7)h(presents)e(an)i(e)-18 b(xample)405 b(sho)-30 b(wing)405 b(ho)-30 b(w)406 b(these)f(concepts)g(are)h(emplo)-12 b(yed)406 b(in)f(the)5978 27600 y(DJ)466 b(library)-79 b(.)869 b(Section)467 b(8)h(discusses)e(related)h(w)-12 b(ork.)869 b(Finally)-79 b(,)508 b(section)468 b(9)f(presents)f(some) 5978 29106 y(conclusions)302 b(and)h(ideas)g(for)g(further)f(de)-30 b(v)-18 b(elopment.)5978 32923 y Ft(2)1328 b(Notation)5978 35092 y Fs(W)-97 b(e)311 b(will)h(be)g(using)f(relations)g(as)g(our)g (fundamental)h(tool,)h(so)e(we)h(will)g(need)g(some)f(notation)5978 36598 y(for)302 b(dealing)h(with)h(relations.)7859 38495 y(If)289 b Fq(A)g Fs(and)h Fq(B)f Fs(are)g(sets,)i(a)f(relation)f(from) g Fq(A)g Fs(to)g Fq(B)g Fs(is)g(a)h(subset)e Fq(R)h Fs(of)h Fq(A)156 b Fh(\002)g Fq(B)p Fs(.)368 b(If)289 b Fq(a)p Fp(;)135 b Fq(b)255 b Fh(2)h Fq(R)p Fs(,)292 b(we)5978 40000 y(will)337 b(write)g Fq(R)p Fi(\()p Fq(a)p Fp(;)135 b Fq(b)p Fi(\))p Fs(,)343 b Fq(a)288 b(R)g(b)338 b Fs(,)346 b(and)337 b Fi(\()p Fq(a)p Fp(;)135 b Fq(b)p Fi(\))286 b Fh(2)i Fq(R)336 b Fs(interchangebly)-79 b(.)480 b(A)337 b(relation)h(from)e Fq(A)h Fs(to)h Fq(A)f Fs(is)5978 41506 y(often)302 b(called)i(a)f(relation)g Fq(on)g(A)p Fs(.)7859 43403 y(W)-97 b(e)475 b(denote)f(composition)g(of)g (relations)f(by)h(concatenation)h Fq(e)-18 b(.g)g(.)474 b(x)368 b Fi(\()p Fq(RS)10 b Fi(\))363 b Fq(z)473 b Fs(if)-30 b(f)473 b(there)5978 44908 y(e)-18 b(xists)293 b(a)h Fq(y)g Fs(such)g(that)g Fq(x)264 b(R)d(y)294 b Fs(and)g Fq(y)262 b(S)270 b(z)p Fs(.)373 b(W)-97 b(e)294 b(also)g(write)f Fq(x)265 b(R)c(y)g(S)271 b(z)p Fs(.)372 b Fq(R)35090 44468 y Fo(\003)35882 44908 y Fs(denotes)293 b(the)i(re\003e)-18 b(xi)-30 b(v)-18 b(e)5978 46413 y(transiti)-30 b(v)-18 b(e)302 b(closure)g(of)h Fq(R)p Fs(.)7859 48310 y(W)-97 b(e)434 b(often)g(think)g(of)f(directed)h(graphs)f(as)g(relations)g (\(and)h(vice)g(v)-18 b(ersa\),)465 b(so)433 b(we)h(write)5917 49816 y Fq(C)27 b Fi(\()p Fq(c)7761 49998 y Fm(1)8259 49816 y Fp(;)135 b Fq(c)9269 49998 y Fm(2)9765 49816 y Fi(\))315 b Fs(or)g Fq(c)12414 49998 y Fm(1)13127 49816 y Fq(C)304 b(c)14777 49998 y Fm(2)15591 49816 y Fs(when)316 b(there)f(is)g(an)g(edge)h(from)f Fq(c)29667 49998 y Fm(1)30480 49816 y Fs(to)g Fq(c)32276 49998 y Fm(2)33090 49816 y Fs(in)254 b Fq(C)27 b Fs(.)414 b(W)-97 b(e)315 b(tak)-12 b(e)316 b(as)f(gi)-30 b(v)-18 b(en)315 b(the)5978 51321 y(de\002nition)303 b(of)g(a)g(path)g(in)g(a)g(directed)g(graph.) 5978 55138 y Ft(3)1328 b(The)332 b(Model)5978 57308 y Ff(De\002nition)302 b(1)606 b Fq(A)341 b Fs(class)g(graph)h Fq(\(sometimes)e(called)i(a)g Fs(class)e(diagram)p Fq(\))h(consists)g (of)g(a)h(set)280 b(C)5978 58813 y(\(of)c(\223classes\224\),)k(a)d(set) f(E)365 b(\(of)276 b(\002eld)h(names\),)282 b(for)276 b(eac)-18 b(h)277 b(e)245 b Fh(2)f Fq(E)365 b(a)277 b(r)-45 b(elation)276 b(\(also)g(named)i(e\))e(on)5978 60319 y(classes)299 b(\(\223has)g(part)h(named)h(e\224\),)f(and)h(a)f(r)-45 b(e\003e)-24 b(xive)-12 b(,)301 b(tr)-18 b(ansitive)299 b(r)-45 b(elation)301 b Fh(\024)e Fq(on)h(classes)f(\(\223is)5978 61824 y(a)k(subclass)f(of)112 b(\224\).)374 b(W)-112 b(e)304 b(write)242 b(C)27 b Fi(\()p Fq(c)20426 62006 y Fm(1)20924 61824 y Fp(;)135 b Fq(c)21934 62006 y Fm(2)22431 61824 y Fi(\))302 b Fq(if)-22 b(f)303 b(ther)-45 b(e)303 b(e)-24 b(xists)302 b(e)270 b Fh(2)e Fq(E)391 b(suc)-18 b(h)303 b(that)g(e)p Fi(\()p Fq(c)39476 62006 y Fm(1)39974 61824 y Fp(;)135 b Fq(c)40984 62006 y Fm(2)41481 61824 y Fi(\))p Fq(.)7859 64846 y Fs(Each)344 b(relation)g Fq(e)h Fs(codes)f(the)g(ef)-30 b(fect)343 b(of)h(\002nding)g(the)g Fq(e)g Fs(part)g(of)g(an)g(object.)499 b(Usually)344 b(the)5978 66351 y(relation)456 b Fq(e)h Fs(is)e(a)i(partial)f (function)h(\(that)f(is,)494 b(for)456 b(an)-18 b(y)456 b Fq(c)30321 66533 y Fm(1)30820 66351 y Fs(,)494 b(there)457 b(is)f(at)g(most)g(one)h Fq(c)42652 66533 y Fm(2)43606 66351 y Fs(such)25600 69672 y(2)p eop %%Page: 3 3 3 2 bop 5978 7638 a Fs(that)374 b Fq(e)p Fi(\()p Fq(c)9717 7820 y Fm(1)10215 7638 y Fp(;)135 b Fq(c)11225 7820 y Fm(2)11721 7638 y Fi(\))p Fs(\),)391 b(b)-24 b(ut)375 b(we)f(will)g(not)h(need)f(this)g(property)-79 b(.)590 b(When)374 b Fq(e)p Fi(\()p Fq(c)35685 7820 y Fm(1)36183 7638 y Fp(;)135 b Fq(c)37193 7820 y Fm(2)37690 7638 y Fi(\))p Fs(,)391 b(we)375 b(sometimes)5978 9143 y(say)369 b(that)g Fq(c)10688 9325 y Fm(1)11556 9143 y Fs(has)g(an)h Fq(e)p Fs(-part)f(of)g(type)g Fq(c)22624 9325 y Fm(2)23123 9143 y Fs(.)574 b(\(The)369 b(signi\002cance)h(of)f(the)g(w)-12 b(ord)370 b(\223type\224)g(will)f(be)5978 10649 y(e)-18 b(xplained)286 b(momentarily\).)370 b(W)-97 b(e)287 b(use)f Fh(\024)g Fs(to)g(denote)h(the)f(re\003e)-18 b(xi)-30 b(v)-18 b(e,)290 b(transiti)-30 b(v)-18 b(e)285 b(closure)h(of)g(the) 5978 12154 y(inheritance)320 b(relation,)k(so)c Fq(c)278 b Fh(\024)g Fq(c)19986 11714 y Fo(0)20605 12154 y Fs(means)320 b(that)g Fq(c)g Fs(is)f(either)h(the)g(same)g(as)g Fq(c)37706 11714 y Fo(0)38325 12154 y Fs(or)f(is)h(one)g(of)g Fq(c)44721 11714 y Fo(0)45020 12154 y Fs(')-67 b(s)5978 13660 y(descendants.)7859 15557 y(W)-97 b(e)288 b(use)225 b Fq(C)314 b Fs(to)287 b(denote)g(the)g(entire)g(class)f(graph)h Fh(h)-61 b Fq(C)27 b Fp(;)135 b Fq(E)88 b Fp(;)135 b Fh(\024i)p Fs(.)365 b(W)-97 b(e)287 b(write)g Fh(\025)e Fs(for)h(the)h(in)-48 b(v)-18 b(erse)5978 17062 y(of)302 b Fh(\024)p Fs(.)7859 18959 y(An)267 b(object)f(graph)g(is)g(a)g(model)g(of)g(the)h(objects,) 273 b(represented)266 b(in)g(the)g(heap)h(or)e(else)-30 b(where,)5978 20465 y(and)303 b(their)g(references)f(to)h(each)h (other:)5978 23690 y Ff(De\002nition)e(2)606 b Fq(If)242 b(C)331 b(is)302 b(a)h(class)f(gr)-18 b(aph,)303 b(then)g(an)g Fs(object)h(graph)f Fq(for)241 b(C)331 b(consists)302 b(of:)7493 26583 y(1.)606 b(a)303 b(set)g(O)g(\(of)f (\223objects\224\),)7493 29085 y(2.)606 b(a)303 b(map)g Fs(class)269 b(:)g Fq(O)h Fh(!)208 b Fq(C)27 b(,)304 b(and)7493 31586 y(3.)606 b(for)302 b(eac)-18 b(h)304 b(e)269 b Fh(2)g Fq(E)88 b(,)303 b(a)g(r)-45 b(elation)303 b(\(also)f(denoted)i(e\))f(on)g(O)5978 34480 y(suc)-18 b(h)302 b(that)h(if)g(e)p Fi(\()p Fq(o)13265 34662 y Fm(1)13763 34480 y Fp(;)135 b Fq(o)14841 34662 y Fm(2)15338 34480 y Fi(\))p Fq(,)302 b(then)19217 37203 y Fs(class)o Fi(\()p Fq(o)22650 37385 y Fm(1)23148 37203 y Fi(\))268 b(\()p Fh(\024)g Fq(e)h Fh(\025)p Fi(\))f Fq(cl)62 b(ass)p Fi(\()p Fq(o)31622 37385 y Fm(2)32118 37203 y Fi(\))7859 40317 y Fq(W)-112 b(e)304 b(say)f(that)g(o)g(is)f(of)480 b Fs(type)303 b Fq(c)h(when)f Fs(class)p Fi(\()p Fq(o)p Fi(\))268 b Fh(\024)g Fq(c.)7859 43542 y Fs(An)402 b(object)h(is)e(of)g (type)h Fq(c)g Fs(when)g(its)f(class)h(is)f(some)g(class)g(that)h(is)f (a)h(descendant)h(of)e Fq(c)p Fs(.)5978 45048 y(This)307 b(corresponds)h(to)h(the)f(usual)h(e)-18 b(xpectation)309 b(in)g(a)f(typed)h(object-oriented)g(language:)388 b(if)308 b(a)5978 46553 y(v)-30 b(ariable)291 b(is)g(of)g(type)h Fq(c)p Fs(,)i(its)d(v)-30 b(alue)291 b(is)g(either)h(null)f(or)h(is)f (an)g(object)h(whose)g(class)e(is)h(either)h Fq(c)f Fs(or)5978 48059 y(a)303 b(descendent)g(of)g Fq(c)p Fs(.)7859 49956 y(The)417 b(tra)-24 b(v)-18 b(ersal)416 b(of)h(an)g(edge)h(labeled)g Fq(e)f Fs(corresponds)f(to)h(retrie)-30 b(ving)417 b(the)g(v)-30 b(alue)417 b(of)g(the)5978 51461 y Fq(e)380 b Fs(\002eld.)608 b(Condition)380 b(3)h(captures)f(the)g(notion)h(that)f(e)-30 b(v)-18 b(ery)380 b(edge)h(in)f(the)g(object)h(graph)f(is)g(an)5978 52967 y(image)286 b(of)g(a)g(has-as-part)f(edge)h(in)g(the)g(class)g (graph:)367 b(There)286 b(is)f(an)i(edge)f Fq(e)p Fi(\()p Fq(o)38454 53149 y Fm(1)38952 52967 y Fp(;)135 b Fq(o)40030 53149 y Fm(2)40526 52967 y Fi(\))286 b Fs(in)g Fq(O)g Fs(only)5978 54472 y(when)275 b(there)g(e)-18 b(xist)275 b(classes)f Fq(c)18302 54654 y Fm(1)19075 54472 y Fs(and)i Fq(c)21639 54654 y Fm(2)22412 54472 y Fs(such)f(that)h Fq(o)27609 54654 y Fm(1)28382 54472 y Fs(is)e(of)h(type)h Fq(c)33651 54654 y Fm(1)34149 54472 y Fs(,)281 b Fq(c)35271 54654 y Fm(1)36044 54472 y Fs(has)275 b(an)g Fq(e)p Fs(-part)g(of)g (type)5978 55978 y Fq(c)6516 56160 y Fm(2)7014 55978 y Fs(,)303 b(and)g Fq(o)10279 56160 y Fm(2)11080 55978 y Fs(is)g(of)g(type)g Fq(c)16433 56160 y Fm(2)16931 55978 y Fs(,)g(that)h(is,)18379 58701 y(class)o Fi(\()p Fq(o)21812 58883 y Fm(1)22310 58701 y Fi(\))269 b Fh(\024)f Fq(c)24799 58883 y Fm(1)25566 58701 y Fq(e)i(c)26912 58883 y Fm(2)27680 58701 y Fh(\025)402 b Fs(class)p Fi(\()p Fq(o)32459 58883 y Fm(2)32956 58701 y Fi(\))5978 61424 y Fs(See)303 b(\002gure)g(1.)7859 63321 y(As)347 b(we)g(did)h(for)e(class)g(graphs,)358 b(we)347 b(use)g Fq(O)g Fs(to)g(denote)h(the)f(entire)g(object)g(graph) g(whose)5978 64826 y(set)302 b(of)h(objects)g(is)f Fq(O)p Fs(.)25600 69672 y(3)p eop %%Page: 4 4 4 3 bop 6236 24643 a @beginspecial 0 @llx 0 @lly 354 @urx 164 @ury 3540 @rwi @setspecial%%BeginDocument: single-link.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: single-link.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Fri May 31 16:06:16 2002 %%For: wand@alnilam.ccs.neu.edu (Mitchell Wand) %%Orientation: Portrait %%BoundingBox: 0 0 354 164 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 0.7500 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -12.0 217.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 5812 m -1000 -1000 l 9112 -1000 l 9112 5812 l cp clip 0.04500 0.04500 sc % Polyline 7.500 slw n 2100 1200 m 2700 1200 l 2700 1800 l 2100 1800 l cp gs col0 s gr % Polyline n 4200 1200 m 4800 1200 l 4800 1800 l 4200 1800 l cp gs col0 s gr % Polyline n 1500 2400 m 2100 2400 l 2100 3000 l 1500 3000 l cp gs col0 s gr % Polyline n 4800 2400 m 5400 2400 l 5400 3000 l 4800 3000 l cp gs col0 s gr % Polyline n 1500 4200 m 2100 4200 l 2100 4800 l 1500 4800 l cp gs col0 s gr % Polyline n 4800 4200 m 5400 4200 l 5400 4800 l 4800 4800 l cp gs col0 s gr % Polyline [15 45] 45 sd gs clippath 1770 3147 m 1800 3027 l 1830 3147 l 1830 2985 l 1770 2985 l cp clip n 1800 4200 m 1800 3000 l gs col0 s gr gr [] 0 sd % arrowhead n 1770 3147 m 1800 3027 l 1830 3147 l 1800 3147 l 1770 3147 l cp gs 0.00 setgray ef gr col0 s % Polyline [15 45] 45 sd gs clippath 5070 3147 m 5100 3027 l 5130 3147 l 5130 2985 l 5070 2985 l cp clip n 5100 4200 m 5100 3000 l gs col0 s gr gr [] 0 sd % arrowhead n 5070 3147 m 5100 3027 l 5130 3147 l 5100 3147 l 5070 3147 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 4653 4470 m 4773 4500 l 4653 4530 l 4815 4530 l 4815 4470 l cp clip n 2100 4500 m 4800 4500 l gs col0 s gr gr % arrowhead n 4653 4470 m 4773 4500 l 4653 4530 l 4653 4500 l 4653 4470 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 4053 1470 m 4173 1500 l 4053 1530 l 4215 1530 l 4215 1470 l cp clip n 2700 1500 m 4200 1500 l gs col0 s gr gr % arrowhead n 4053 1470 m 4173 1500 l 4053 1530 l 4053 1500 l 4053 1470 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 2275 1883 m 2380 1819 l 2317 1925 l 2432 1811 l 2389 1768 l cp clip n 1800 2400 m 2400 1800 l gs col0 s gr gr % arrowhead n 2275 1883 m 2380 1819 l 2317 1925 l 2296 1904 l 2275 1883 l cp gs col7 1.00 shd ef gr col0 s % Polyline gs clippath 4583 1925 m 4519 1819 l 4625 1883 l 4511 1768 l 4468 1811 l cp clip n 5100 2400 m 4500 1800 l gs col0 s gr gr % arrowhead n 4583 1925 m 4519 1819 l 4625 1883 l 4604 1904 l 4583 1925 l cp gs col7 1.00 shd ef gr col0 s % Polyline [60] 0 sd n 300 3600 m 8100 3600 l gs col0 s gr [] 0 sd % Polyline n 1500 2475 m 2100 2475 l gs col0 s gr % Polyline n 2100 1275 m 2700 1275 l gs col0 s gr % Polyline n 4200 1275 m 4800 1275 l gs col0 s gr % Polyline n 4800 2475 m 5400 2475 l gs col0 s gr % Polyline gs clippath 1354 4533 m 1475 4511 l 1378 4588 l 1526 4521 l 1501 4466 l cp clip n 675 4425 m 678 4427 l 684 4432 l 695 4440 l 711 4451 l 732 4466 l 756 4484 l 784 4503 l 812 4522 l 841 4541 l 868 4558 l 895 4574 l 920 4589 l 943 4601 l 965 4611 l 986 4620 l 1006 4626 l 1025 4632 l 1044 4635 l 1063 4638 l 1082 4639 l 1101 4638 l 1121 4637 l 1142 4634 l 1165 4629 l 1189 4623 l 1215 4615 l 1244 4606 l 1274 4595 l 1306 4583 l 1339 4570 l 1372 4556 l 1404 4543 l 1433 4530 l 1458 4519 l 1500 4500 l gs col0 s gr gr % arrowhead n 1354 4533 m 1475 4511 l 1378 4588 l 1366 4561 l 1354 4533 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 5532 4571 m 5425 4507 l 5549 4514 l 5394 4467 l 5377 4524 l cp clip n 5925 4425 m 5925 4426 l 5923 4429 l 5919 4438 l 5913 4453 l 5904 4471 l 5893 4492 l 5882 4512 l 5870 4531 l 5857 4547 l 5845 4561 l 5832 4571 l 5819 4579 l 5804 4584 l 5788 4588 l 5774 4589 l 5758 4589 l 5741 4588 l 5722 4586 l 5701 4582 l 5676 4577 l 5649 4571 l 5618 4563 l 5585 4555 l 5551 4545 l 5516 4535 l 5483 4525 l 5454 4516 l 5430 4509 l 5400 4500 l gs col0 s gr gr % arrowhead n 5532 4571 m 5425 4507 l 5549 4514 l 5541 4542 l 5532 4571 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 5511 2800 m 5423 2713 l 5542 2749 l 5402 2667 l 5372 2718 l cp clip n 6075 2775 m 6075 2776 l 6074 2779 l 6071 2787 l 6066 2801 l 6058 2819 l 6049 2841 l 6039 2864 l 6027 2886 l 6015 2907 l 6003 2924 l 5990 2938 l 5977 2949 l 5963 2957 l 5948 2962 l 5931 2963 l 5913 2963 l 5899 2961 l 5885 2957 l 5869 2953 l 5852 2947 l 5834 2940 l 5814 2931 l 5791 2921 l 5767 2909 l 5740 2895 l 5711 2880 l 5679 2862 l 5646 2844 l 5612 2825 l 5577 2805 l 5543 2785 l 5510 2766 l 5481 2748 l 5455 2733 l 5434 2720 l 5400 2700 l gs col0 s gr gr % arrowhead n 5511 2800 m 5423 2713 l 5542 2749 l 5527 2775 l 5511 2800 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 1361 2756 m 1477 2714 l 1394 2806 l 1529 2717 l 1496 2667 l cp clip n 750 2775 m 751 2779 l 753 2786 l 757 2799 l 763 2817 l 770 2839 l 779 2864 l 789 2890 l 800 2915 l 811 2938 l 823 2958 l 835 2975 l 848 2989 l 861 2999 l 875 3007 l 890 3011 l 907 3013 l 925 3013 l 940 3010 l 956 3007 l 973 3002 l 992 2995 l 1013 2987 l 1035 2976 l 1061 2964 l 1088 2950 l 1118 2933 l 1151 2915 l 1186 2894 l 1223 2872 l 1262 2849 l 1301 2825 l 1339 2801 l 1376 2779 l 1409 2758 l 1438 2739 l 1462 2725 l 1500 2700 l gs col0 s gr gr % arrowhead n 1361 2756 m 1477 2714 l 1394 2806 l 1377 2781 l 1361 2756 l cp gs 0.00 setgray ef gr col0 s /Times-Italic ff 180.00 scf sf 3300 4425 m gs 1 -1 sc (e) col0 sh gr /Times-Italic ff 180.00 scf sf 600 4350 m gs 1 -1 sc (o1) col0 sh gr /Times-Italic ff 180.00 scf sf 5850 4350 m gs 1 -1 sc (o2) col0 sh gr /Times-Italic ff 180.00 scf sf 450 2700 m gs 1 -1 sc (class\(o1\)) col0 sh gr /Times-Italic ff 180.00 scf sf 5775 2700 m gs 1 -1 sc (class\(o2\)) col0 sh gr /Times-Italic ff 180.00 scf sf 6600 3225 m gs 1 -1 sc (class graph) col0 sh gr /Times-Italic ff 180.00 scf sf 6600 3975 m gs 1 -1 sc (object graph) col0 sh gr /Times-Italic ff 180.00 scf sf 3300 1425 m gs 1 -1 sc (e) col0 sh gr $F2psEnd rs %%EndDocument @endspecial 5978 27255 a Fs(Figure)318 b(1:)407 b(T)-97 b(ypical)318 b(link)h(in)f(an)h(object)g(graph.)422 b(If)318 b(there)h(is)f(an)g Fq(e)p Fs(-edge)h(from)f Fq(o)p Fs(1)h(to)f Fq(o)p Fs(2,)323 b(then)5978 28760 y(there)303 b(is)f(a)h(path)h(class) o Fi(\()p Fq(o)p Fs(1)p Fi(\))268 b Fh(\024)p Fq(e)p Fh(\025)402 b Fs(class)o Fi(\()p Fq(o)p Fs(2)p Fi(\))302 b Fs(in)h(the)g(class)f(graph.)7859 35026 y(All)421 b(parts)g(are)f (optional)i(\(allo)-30 b(wing)420 b(for)g(null)h(v)-30 b(alues\))420 b(or)h(multi-v)-30 b(alued)420 b(\(for)g(a)h(gi)-30 b(v)-18 b(en)5978 36531 y(object)288 b Fq(o)9834 36713 y Fm(1)10332 36531 y Fs(,)j(there)c(may)h(be)g(man)-18 b(y)288 b(objects)f Fq(o)24733 36713 y Fm(2)25519 36531 y Fs(such)g(that)h Fq(e)p Fi(\()p Fq(o)31749 36713 y Fm(1)32247 36531 y Fp(;)135 b Fq(o)33325 36713 y Fm(2)33821 36531 y Fi(\))p Fs(\).)370 b(The)288 b(latter)f(case)h(allo)-30 b(ws)5978 38037 y(us)320 b(to)g(handle)h(collections:)410 b(if)320 b(class)g Fq(c)22466 38219 y Fm(1)23285 38037 y Fs(contains)g(a)g(\002eld)h Fq(e)f Fs(that)h(is)f(a)g(collection)h (of)f(objects)5978 39542 y(of)424 b(type)h Fq(c)10462 39724 y Fm(2)10960 39542 y Fs(,)455 b(we)425 b(may)f(represent)g(this)g (as)g Fq(e)p Fi(\()p Fq(c)26091 39724 y Fm(1)26589 39542 y Fp(;)135 b Fq(c)27599 39724 y Fm(2)28096 39542 y Fi(\))424 b Fs(and)g(use)h(multi-v)-30 b(alued)424 b(edges)g(in)h(the)5978 41048 y(object)303 b(graph,)g(rather)g(than)g(introduce)g(the)g(notion) h(of)e(collections)h(into)g(our)g(model.)7859 42945 y(W)-97 b(e)324 b(might)g(propose)e(the)i(additional)g(condition)f(that)h(if)f (class)o Fi(\()p Fq(o)35599 43127 y Fm(1)36097 42945 y Fi(\))280 b Fh(\024)f Fq(c)38608 43127 y Fm(1)39430 42945 y Fs(and)323 b Fq(e)p Fi(\()p Fq(c)43050 43127 y Fm(1)43548 42945 y Fp(;)135 b Fq(c)44558 43127 y Fm(2)45055 42945 y Fi(\))p Fs(,)5978 44450 y(then)462 b(there)g(e)-18 b(xists)461 b(an)h Fq(o)16829 44632 y Fm(2)17789 44450 y Fs(such)g(that)g Fq(e)p Fi(\()p Fq(o)24368 44632 y Fm(1)24865 44450 y Fp(;)135 b Fq(o)25943 44632 y Fm(2)26440 44450 y Fi(\))461 b Fs(and)h(class)p Fi(\()p Fq(o)33018 44632 y Fm(2)33515 44450 y Fi(\))357 b Fh(\024)f Fq(c)36180 44632 y Fm(2)36679 44450 y Fs(.)852 b(This)461 b(means)h(that)5978 45956 y(e)-30 b(v)-18 b(ery)274 b(edge)g(predicted)h(by)f(the)h(class)e (graph)i(e)-18 b(xists)273 b(in)h(the)h(object)g(graph.)366 b(All)274 b(the)h(theorems)5978 47461 y(in)360 b(the)g(paper)g(are)g (true)f(under)h(this)g(stronger)f(de\002nition,)374 b(b)-24 b(ut)360 b(the)g(additional)g(condition)h(is)5978 48966 y(undesirable)302 b(because)i(it)f(rules)f(out)h(null)g(\002elds.)5978 52817 y Ft(4)1328 b(The)332 b(Pr)-24 b(oblem)5978 54986 y Fs(The)302 b(computational)i(problem)f(we)g(wish)g(to)g(study)g(is)f (the)i(follo)-30 b(wing:)7859 56883 y(W)-97 b(e)466 b(are)g(at)f(an)h (object)f Fq(o)h Fs(of)f(class)f Fq(c)i Fs(in)f(object)h(graph)f Fq(O)h Fs(and)g(we)f(wish)g(to)h(\002nd)f(all)5978 58389 y(reachable)407 b(objects)f(of)h(type)g Fq(c)19317 57949 y Fo(0)19616 58389 y Fs(.)686 b(Ho)-30 b(we)g(v)-18 b(er)-48 b(,)432 b(we)407 b(ha)-24 b(v)-18 b(e)407 b(no)g(information)f(about)h (the)g(object)5978 59894 y(graph)291 b(other)h(than)g(that)g(it)g(is)f (a)h(le)-18 b(g)-6 b(al)292 b(object)g(graph)g(for)230 b Fq(C)27 b Fs(.)373 b(Which)292 b(edges)g(must)f(we)h(e)-18 b(xplore)5978 61400 y(in)303 b(order)f(to)h(\002nd)g(all)g(these)g (objects?)7859 63296 y(W)-97 b(e)304 b(can)g(formalize)g(the)g(problem) f(as)g(follo)-30 b(ws.)377 b(F)-18 b(or)303 b(each)h(pair)g(of)f (classes)f Fq(c)i Fs(and)g Fq(c)43509 62857 y Fo(0)43808 63296 y Fs(,)g(we)5978 64802 y(need)394 b(to)h(\002nd)f(a)h(set)f (FIRST)p Fi(\()p Fq(c)p Fp(;)135 b Fq(c)20272 64362 y Fo(0)20569 64802 y Fi(\))393 b Fs(such)h(that)h Fq(e)320 b Fh(2)g Fs(FIRST)o Fi(\()p Fq(c)p Fp(;)135 b Fq(c)33567 64362 y Fo(0)33864 64802 y Fi(\))394 b Fs(if)-30 b(f)393 b(it)i(is)e(possible)h(for)g(an)5978 66307 y(object)349 b(of)f(class)h Fq(c)g Fs(to)f(reach)h(an)h(object)f(of)f(type)h Fq(c)27641 65867 y Fo(0)28289 66307 y Fs(by)g(a)g(path)g(be)-18 b(ginning)350 b(with)f(an)g(edge)g Fq(e)p Fs(.)25600 69672 y(4)p eop %%Page: 5 5 5 4 bop 5978 7638 a Fs(More)302 b(precisely)-79 b(,)10257 10282 y(FIRST)p Fi(\()p Fq(c)p Fp(;)135 b Fq(c)15577 9781 y Fo(0)15874 10282 y Fi(\))268 b(=)g Fh(f)p Fq(e)i Fh(2)f Fq(E)357 b Fh(j)268 b Fs(there)303 b(e)-18 b(xists)302 b(an)h(object)h(graph)f Fq(O)g Fs(of)242 b Fq(C)330 b Fs(and)22018 11787 y(objects)303 b Fq(o)g Fs(and)g Fq(o)29323 11347 y Fo(0)29925 11787 y Fs(such)g(that:)23230 13293 y(1.)376 b(class)o Fi(\()p Fq(o)p Fi(\))268 b(=)g Fq(c)p Fs(,)23230 14798 y(2.)376 b(class)o Fi(\()p Fq(o)27948 14358 y Fo(0)28247 14798 y Fi(\))268 b Fh(\024)g Fq(c)30735 14358 y Fo(0)23230 16304 y Fs(3.)376 b Fq(o)269 b(eO)26803 15864 y Fo(\003)27571 16304 y Fq(o)28177 15864 y Fo(0)28779 16304 y Fh(g)5978 18929 y Fs(The)263 b(last)g(condition,)272 b Fq(o)233 b(eO)17479 18489 y Fo(\003)18210 18929 y Fq(o)18816 18489 y Fo(0)19379 18929 y Fs(says)263 b(that)h(there)f(is)g(a)h(path)g (from)f Fq(o)g Fs(to)h Fq(o)36025 18489 y Fo(0)36588 18929 y Fs(in)f(the)h(object)g(graph,)5978 20434 y(consisting)302 b(of)h(an)g(edge)g(labelled)h Fq(e)p Fs(,)f(follo)-30 b(wed)303 b(by)g(an)-18 b(y)303 b(sequence)h(of)e(edges)h(in)g(the)h (graph.)7859 22331 y(Our)455 b(lack)f(of)g(information)g(about)h(the)f (actual)h(object)g(graph)f(is)g(represented)g(by)g(the)5978 23837 y(e)-18 b(xistential)360 b(operator)-67 b(.)550 b(Since)361 b(we)g(cannot)h(search)e(e)-18 b(xplicitly)362 b(o)-18 b(v)g(er)360 b(all)h(object)g(graphs,)375 b(our)5978 25342 y(goal)303 b(is)f(to)h(\002nd)g(a)h(static)e(algorithm)h(to)g (compute)h(these)f(sets.)5978 29180 y Ft(5)1328 b(T)-98 b(ra)-33 b(v)-13 b(ersal)331 b(Algorithms)5978 31349 y Fs(Before)469 b(considering)h(an)g(algorithm)f(for)g(\002nding)h(the) g(FIRST)f(sets,)511 b(we)470 b(consider)f(some)5978 32855 y(applications)344 b(of)f(these)h(sets.)498 b(W)-97 b(e)345 b(can)f(use)g(these)g(sets)f(to)h(\002nd)g(not)g(just)g(reachable)g (objects)5978 34360 y(of)302 b(a)i(gi)-30 b(v)-18 b(en)302 b(type,)i(b)-24 b(ut)303 b(paths)f(that)i(pass)e(through)h(objects)g (of)f(a)i(gi)-30 b(v)-18 b(en)302 b(type.)5978 37506 y Ff(De\002nition)g(3)606 b Fq(Let)433 b(R)341 b Fi(=)f(\()p Fq(c)17967 37688 y Fm(1)18464 37506 y Fp(;)135 b(:)g(:)g(:)129 b(;)135 b Fq(c)21356 37688 y Fe(K)22049 37506 y Fi(\))432 b Fq(be)h(a)f(non-empty)h(sequence)g(of)f(classes.)763 b(Let)523 b(p)341 b Fi(=)5978 39012 y(\()p Fq(o)7055 39194 y Fm(1)7552 39012 y Fp(;)135 b(:)g(:)g(:)129 b(;)135 b Fq(o)10512 39194 y Fe(N)11209 39012 y Fi(\))357 b Fq(be)h(a)f(path)h (in)g(O.)539 b(W)-112 b(e)358 b(say)f(that)449 b(p)357 b(is)g(an)h(R)p Fs(-path)f Fq(if)-22 b(f)357 b(ther)-45 b(e)358 b(is)f(a)g(subsequence)5978 40517 y(o)6717 40699 y Fe(j)6963 40833 y Fc(1)7405 40517 y Fp(;)135 b(:)g(:)g(:)129 b(;)135 b Fq(o)10498 40699 y Fe(j)10744 40832 y Fb(K)11684 40517 y Fq(\(K)363 b Fh(\025)295 b Fs(1)p Fq(\))351 b(of)442 b(p)351 b(suc)-18 b(h)351 b(that)h(for)e(eac)-18 b(h)352 b(i,)363 b(o)29122 40699 y Fe(j)29368 40832 y Fb(i)30015 40517 y Fq(has)351 b(type)g(c)34958 40699 y Fe(i)35260 40517 y Fq(,)363 b(and)534 b(j)38615 40699 y Fe(K)39605 40517 y Fi(=)295 b Fq(N)425 b(\(that)351 b(is,)5978 42022 y(the)317 b(last)h(element)g(of)g(the)g(path)g(must)f(be)h(part)f(of)h (the)g(subsequence\).)419 b(W)-112 b(e)318 b(say)g(an)g(R-path)f(is) 5978 43528 y Fs(minimal)303 b Fq(if)-22 b(f)303 b(it)g(has)f(no)i (initial)f(se)-48 b(gment)302 b(that)h(is)g(also)f(an)h(R-path.)7859 46674 y Fs(Thus)357 b(an)g Fq(R)p Fs(-path)f(is)h(a)g(path)g(through)g (the)g(object)g(graph)g(that)h(passes)d(through)i(objects)5978 48179 y(of)299 b(the)h(types)g(speci\002ed)g(by)g Fq(R)f Fs(in)h(the)g(order)g(speci\002ed)f(by)h Fq(R)p Fs(.)375 b(It)299 b(may)h(pass)g(through)f(objects)5978 49685 y(of)j(other)h(classes)f(along)i(the)f(w)-12 b(ay)-79 b(,)303 b(b)-24 b(ut)303 b(it)g(must)g(end)g(at)g(the)g(endpoint)h(of)f Fq(R)p Fs(.)7859 51582 y(Gi)-30 b(v)-18 b(en)294 b(an)g(object)g Fq(o)p Fs(,)i(we)e(can)g(visit)f(all)h(the)g(endpoints)g(of)f(minimal)h (R-paths)g(starting)f(at)5978 53087 y Fq(o)303 b Fs(as)f(follo)-30 b(ws:)9008 56233 y Ff(Algorithm)303 b Fq(sear)-45 b(c)-18 b(h)o Fi(\()p Fq(o)p Fp(;)135 b Fq(R)p Fi(\))p Fs(:)9008 58224 y(Let)303 b Fq(c)11465 58406 y Fm(1)11963 58224 y Fs(,)g(.)182 b(.)g(.)g(,)303 b Fq(c)15168 58406 y Fe(n)15969 58224 y Fs(be)g(the)g(classes)f(such)h(that)g Fq(R)269 b Fi(=)g(\()p Fq(c)30746 58406 y Fm(1)31243 58224 y Fp(;)135 b(:)g(:)g(:)129 b(;)135 b Fq(c)34135 58406 y Fe(n)34632 58224 y Fi(\))p Fs(.)10159 60699 y(1.)607 b(If)246 b Fq(o)i Fs(does)f(not)h(ha)-24 b(v)-18 b(e)247 b(type)h Fq(c)23215 60881 y Fm(1)23713 60699 y Fs(,)259 b(then)247 b(for)g(each)h Fq(e)g Fs(in)f(FIRST)p Fi(\()p Fq(cl)62 b(ass)p Fi(\()p Fq(o)p Fi(\))p Fp(;)135 b Fq(c)41531 60881 y Fm(1)42025 60699 y Fi(\))p Fs(,)11675 62204 y(and)303 b(each)g Fq(o)16857 61764 y Fo(0)17459 62204 y Fs(such)g(that)g Fq(e)p Fi(\()p Fq(o)p Fp(;)135 b Fq(o)24798 61764 y Fo(0)25095 62204 y Fi(\))p Fs(,)303 b(do)g Fq(sear)-45 b(c)-18 b(h)o Fi(\()p Fq(o)31932 61764 y Fo(0)32231 62204 y Fp(;)135 b Fq(R)p Fi(\))p Fs(.)10159 64126 y(2.)607 b(If)302 b Fq(o)h Fs(has)g(type)g Fq(c)18541 64308 y Fm(1)19039 64126 y Fs(,)g(and)h Fq(R)269 b Fi(=)f(\()p Fq(c)24929 64308 y Fm(1)25426 64126 y Fi(\))p Fs(,)303 b(then)g(do)g Fq(visit)22 b Fi(\()p Fq(o)p Fi(\))p Fs(.)10159 66048 y(3.)607 b(If)229 b(o)h(has)h(type)f Fq(c)18250 66230 y Fm(1)18748 66048 y Fs(,)245 b(and)231 b Fq(R)202 b Fi(=)g(\()p Fq(c)24374 66230 y Fm(1)24870 66048 y Fp(;)135 b Fq(c)25880 66230 y Fm(2)26377 66048 y Fp(;)g(:)g(:)g(:)128 b(;)135 b Fq(c)29268 66230 y Fe(n)29765 66048 y Fi(\))p Fs(,)244 b(then)231 b(do)f Fq(sear)-45 b(c)-18 b(h)p Fi(\()p Fq(o)p Fp(;)135 b Fi(\()p Fq(c)40270 66230 y Fm(2)40765 66048 y Fp(;)g(:)g(:)g(:)129 b(;)135 b Fq(c)43657 66230 y Fe(n)44153 66048 y Fi(\)\))p Fs(.)25600 69672 y(5)p eop %%Page: 6 6 6 5 bop 7859 7638 a Fs(In)283 b(case)g(1)g(we)g(are)g(not)g(yet)g(on)g (a)g(path,)k(so)c(we)g(follo)-30 b(w)282 b(the)h(FIRST)g(edges)g(to)f (guide)i(us)e(to)5978 9143 y(the)306 b(\002rst)f(goal)h(type)h Fq(c)15282 9325 y Fm(1)15780 9143 y Fs(.)385 b(W)-97 b(e)307 b(can)f(\002nd)g(the)g(required)g(objects)g Fq(o)33018 8704 y Fo(0)33623 9143 y Fs(by)g(retrie)-30 b(ving)306 b(the)g(v)-30 b(alue)306 b(of)5978 10649 y Fq(o)p Fs(')-67 b(s)317 b Fq(e)p Fs(-\002eld.)422 b(In)318 b(case)g(2,)323 b(we)318 b(ha)-24 b(v)-18 b(e)319 b(reached)f(the)h(last)f(goal)g (type,)323 b(so)318 b(we)g(visit)g(the)g(object.)422 b(In)5978 12154 y(case)303 b(3)g(we)g(ha)-24 b(v)-18 b(e)303 b(reached)h(the)f(\002rst)f(goal)h(type,)g(so)g(we)g(recur)g (on)g(the)g(rest)g(of)g(the)g(goal)g(path.)7859 14051 y(W)-97 b(e)318 b(could)f(\002nd)g(all)g Fq(R)p Fs(-paths,)j(instead)d (of)f(just)h(the)g(minimal)g(ones,)j(by)e(modifying)e(step)5978 15557 y(2)303 b(to)g(continue)g(searching:)10164 18648 y(2)10770 18208 y Fo(0)11675 18648 y Fs(If)255 b Fq(o)h Fs(has)f(type)i Fq(c)18353 18830 y Fm(1)18851 18648 y Fs(,)265 b(and)257 b Fq(R)225 b Fi(=)f(\()p Fq(c)24568 18830 y Fm(1)25066 18648 y Fi(\))p Fs(,)265 b(then)256 b(do)g Fq(visit)21 b Fi(\()p Fq(o)p Fi(\))p Fs(.)359 b(Then)256 b(for)f(each)i Fq(e)f Fs(in)11675 20153 y(FIRST)o Fi(\()p Fq(cl)62 b(ass)p Fi(\()p Fq(o)p Fi(\))p Fp(;)135 b Fq(c)20491 20335 y Fm(1)20985 20153 y Fi(\))p Fs(,)244 b(and)231 b(each)f Fq(o)27040 19713 y Fo(0)27570 20153 y Fs(such)g(that)g Fq(e)p Fi(\()p Fq(o)p Fp(;)135 b Fq(o)34763 19713 y Fo(0)35060 20153 y Fi(\))p Fs(,)244 b(do)231 b Fq(sear)-45 b(c)-18 b(h)o Fi(\()p Fq(o)41766 19713 y Fo(0)42064 20153 y Fp(;)135 b Fq(R)p Fi(\))p Fs(.)7859 23244 y(If)303 b(the)g(object)h(graph)f(is)g(ac)-18 b(yclic,)303 b(these)g(algorithms)g(will)g(al)-12 b(w)g(ays)303 b(terminate,)h (since)f(e)-30 b(v-)5978 24750 y(ery)297 b(step)h(either)g(decreases)f (the)i(longest)e(chain)i(of)e(links)h(in)g(the)g(object)g(graph)g(or)g (decreases)5978 26255 y(the)370 b(length)g(of)g Fq(R)p Fs(.)576 b(If)369 b(the)h(graph)g(may)h(be)f(c)-18 b(yclic,)387 b(then)370 b(we)g(need)h(to)f(mark)g(each)g(searched)5978 27761 y(object)283 b(with)h(the)g(state)f Fq(R)g Fs(in)g(which)h(it)f (w)-12 b(as)283 b(reached,)288 b(or)283 b(else)h(carry)f(around)g(the)h (set)f(of)g(pairs)5978 29266 y Fi(\()p Fq(o)p Fp(;)135 b Fq(R)p Fi(\))313 b Fs(that)j(we)h(ha)-24 b(v)-18 b(e)316 b(already)g(searched.)416 b(This)315 b(will)i(allo)-30 b(w)316 b(us)g(to)g(a)-24 b(v)g(oid)316 b(repeated)h(visits)e(to)5978 30772 y(the)303 b(same)g(object)g(in)g(the)g(same)g(tra)-24 b(v)-18 b(ersal)302 b(state.)7859 32668 y(DJ)245 b(allo)-30 b(ws)245 b(the)g(use)g(of)f(a)i(graph,)256 b(called)246 b(a)f Fq(str)-18 b(ate)-48 b(gy)244 b(gr)-18 b(aph)p Fs(,)256 b(to)245 b(specify)g(a)g(more)g(comple)-18 b(x)5978 34174 y(tra)-24 b(v)-18 b(ersal)373 b([9)o(].)589 b(A)374 b(strate)-18 b(gy)374 b(graph)g(can)h(be)f(modeled)h(as)f(a)g (non-deterministic)g(\002nite-state)5978 35679 y(automaton:)5978 38770 y Ff(De\002nition)302 b(4)606 b Fq(A)286 b Fs(strate)-18 b(gy)286 b(graph)g Fq(is)g(given)g(by)h(a)f(set)g(of)g(states)f(Q,)290 b(a)c(r)-45 b(elation)286 b(S)296 b(on)286 b(states,)j(a)5978 40276 y(map)304 b Fs(class)270 b(:)g Fq(Q)g Fh(!)209 b Fq(C)27 b(,)306 b(a)e(set)g(QI)332 b Fh(\022)269 b Fq(Q)304 b(of)h(initial)f(states,)g(and)g(a)h(set)f(QF)372 b Fh(\022)268 b Fq(Q)305 b(of)f(\002nal)h(states.)5978 41781 y(W)-112 b(e)303 b(denote)g(suc)-18 b(h)303 b(a)g(str)-18 b(ate)-48 b(gy)302 b(gr)-18 b(aph)303 b(by)g(S)10 b(.)5978 44872 y Ff(De\002nition)302 b(5)606 b Fq(A)370 b(path)462 b(p)307 b Fi(=)e(\()p Fq(o)19577 45054 y Fm(1)20075 44872 y Fp(;)135 b(:)g(:)g(:)129 b(;)135 b Fq(o)23035 45054 y Fe(N)23732 44872 y Fi(\))370 b Fq(in)g(O)h(is)f(an)h(S)10 b Fs(-path)370 b Fq(if)-22 b(f)370 b(ther)-45 b(e)371 b(is)f(a)g(subsequence)5978 46378 y(o)6717 46560 y Fe(j)6963 46694 y Fc(1)7405 46378 y Fp(;)135 b(:)g(:)g(:)129 b(;)135 b Fq(o)10498 46560 y Fe(j)10744 46693 y Fb(K)11695 46378 y Fq(\(K)369 b Fh(\025)301 b Fs(1)p Fq(\))361 b(of)453 b(p)362 b(and)g(a)g(path)h Fi(\()p Fq(q)24998 46560 y Fm(1)25495 46378 y Fp(;)135 b(:)g(:)g(:)129 b(;)135 b Fq(q)28455 46560 y Fe(K)29148 46378 y Fi(\))361 b Fq(in)h(S)372 b(suc)-18 b(h)362 b(that)g(for)f(eac)-18 b(h)362 b(i,)377 b(o)43241 46560 y Fe(j)43487 46693 y Fb(i)44145 46378 y Fq(has)5978 47883 y(type)320 b Fs(class)o Fi(\()p Fq(q)11750 48065 y Fe(i)12051 47883 y Fi(\))p Fq(,)506 b(j)13668 48065 y Fe(K)14641 47883 y Fi(=)278 b Fq(N)73 b(,)325 b(and)320 b(q)20115 48065 y Fe(K)21089 47883 y Fh(2)278 b Fq(QF)102 b(.)427 b(As)319 b(befor)-45 b(e)-12 b(,)324 b(we)d(say)f(that)g(an)h(S)10 b(-path)319 b(is)h Fs(minimal)5978 49389 y Fq(if)-22 b(f)303 b(it)g(has)f(no)h(initial)g(se)-48 b(gment)303 b(that)g(is)g(also)f(an)h(S)10 b(-path.)7859 52480 y Fs(Gi)-30 b(v)-18 b(en)308 b(an)g(object)g Fq(o)p Fs(,)h(we)e(can)h(visit)f(all)h(the)g(endpoints)f(of)h(minimal)f Fq(S)10 b Fs(-paths)307 b(starting)g(at)5978 53985 y Fq(o)c Fs(as)f(follo)-30 b(ws,)302 b(where)i Fq(Q)16551 53545 y Fo(0)17153 53985 y Fs(ranges)e(o)-18 b(v)g(er)303 b(subsets)f(of)g Fq(Q)p Fs(:)9008 57076 y Ff(Algorithm)230 b Fq(sear)-45 b(c)-18 b(h)o Fi(\()p Fq(o)p Fp(;)135 b Fq(S)10 b Fi(\))202 b Fs(:)g Fq(sear)-45 b(c)-18 b(h)24336 56588 y Fo(0)24634 57076 y Fi(\()p Fq(o)p Fp(;)135 b Fq(QI)62 b Fi(\))p Fs(,)242 b(where)230 b(for)g(an)-18 b(y)230 b Fq(Q)36212 56636 y Fo(0)36713 57076 y Fh(\022)202 b Fq(Q)p Fs(,)244 b Fq(sear)-45 b(c)-18 b(h)42449 56588 y Fo(0)42748 57076 y Fi(\()p Fq(o)p Fp(;)135 b Fq(Q)45172 56636 y Fo(0)45468 57076 y Fi(\))9008 58582 y Fs(is)302 b(de\002ned)i(by:)11675 61348 y Ff(Pr)-22 b(ocedur)g(e)303 b Fq(sear)-45 b(c)-18 b(h)20488 60861 y Fo(0)20787 61348 y Fi(\()p Fq(o)p Fp(;)135 b Fq(Q)23211 60908 y Fo(0)23507 61348 y Fi(\))p Fs(:)12426 63340 y(1.)606 b(If)466 b Fq(cl)62 b(ass)p Fi(\()p Fq(o)p Fi(\))358 b Fh(6\024)h Fs(class)o Fi(\()p Fq(q)p Fi(\))466 b Fs(for)g(an)-18 b(y)466 b Fq(q)361 b Fh(2)e Fq(Q)32367 62900 y Fo(0)32666 63340 y Fs(,)508 b(then)467 b(for)f(each)13941 64846 y Fq(q)342 b Fh(2)g Fq(Q)16914 64406 y Fo(0)17213 64846 y Fs(,)467 b(for)433 b(each)i Fq(e)f Fs(in)g(FIRST)p Fi(\()p Fq(cl)62 b(ass)p Fi(\()p Fq(o)p Fi(\))p Fp(;)135 b Fq(cl)62 b(ass)p Fi(\()p Fq(q)p Fi(\)\))p Fs(,)459 b(and)13941 66351 y(each)304 b Fq(o)17071 65911 y Fo(0)17673 66351 y Fs(such)f(that)g Fq(e)p Fi(\()p Fq(o)p Fp(;)135 b Fq(o)25012 65911 y Fo(0)25309 66351 y Fi(\))p Fs(,)302 b Fq(sear)-45 b(c)-18 b(h)29553 65863 y Fo(0)29852 66351 y Fi(\()p Fq(o)30929 65911 y Fo(0)31228 66351 y Fp(;)135 b Fq(Q)32575 65911 y Fo(0)32872 66351 y Fi(\))p Fs(.)25600 69672 y(6)p eop %%Page: 7 7 7 6 bop 12426 7638 a Fs(2.)606 b(If)230 b Fq(cl)62 b(ass)p Fi(\()p Fq(o)p Fi(\))202 b Fh(\024)g Fs(class)l Fi(\()p Fq(q)p Fi(\))229 b Fs(for)g(some)h Fq(q)202 b Fh(2)g Fq(Q)31616 7198 y Fo(0)32016 7638 y Fh(\\)101 b Fq(QF)f Fs(,)245 b(then)231 b Fq(visit)21 b Fi(\()p Fq(o)p Fi(\))p Fs(.)12426 9365 y(3.)606 b(Otherwise)230 b(let)h Fq(Q)21471 8925 y Fo(00)22215 9365 y Fi(=)202 b Fh(f)p Fq(q)g Fh(2)g Fq(Q)26659 8925 y Fo(0)27226 9365 y Fh(j)268 b Fq(o)230 b Fs(does)g(not)h(ha)-24 b(v)-18 b(e)230 b(type)h Fq(cl)62 b(ass)p Fi(\()p Fq(q)p Fi(\))p Fh(g)101 b([)13941 10870 y(f)p Fq(q)15153 10430 y Fo(0)15452 10870 y Fh(j9)243 b Fq(q)216 b Fh(2)f Fq(Q)19425 10430 y Fo(0)19969 10870 y Fs(such)244 b(that)h Fq(o)g Fs(has)f(type)h(class)p Fi(\()p Fq(q)p Fi(\))e Fs(and)i Fq(S)10 b Fi(\()p Fq(q)p Fp(;)135 b Fq(q)38455 10430 y Fo(0)38752 10870 y Fi(\))p Fh(g)p Fs(.)13941 12376 y(Then)303 b Fq(sear)-45 b(c)-18 b(h)19904 11888 y Fo(0)20202 12376 y Fi(\()p Fq(o)p Fp(;)135 b Fq(Q)22626 11936 y Fo(00)23167 12376 y Fi(\))p Fs(.)7859 15601 y(This)292 b(algorithm)g(is)f(much)h(lik)-12 b(e)292 b(the)h(preceding)f(one,)j(e)-18 b(xcept)292 b(that)g(the)h(set)e Fq(Q)40523 15161 y Fo(0)41114 15601 y Fs(maintains)5978 17107 y(the)430 b(state)g(of)f(a)i(run)e(through)h(the)h (non-deterministic)e(automaton)i Fq(S)10 b Fs(.)756 b(In)430 b(step)g(1,)462 b(we)430 b(are)5978 18612 y(not)405 b(at)g(a)g(point)h (on)f(the)g(subsequence,)431 b(so)405 b(we)g(use)g(the)g(FIRST)g(sets)f (to)i(search)e(an)-18 b(y)406 b(edge)5978 20117 y(that)328 b(may)h(lead)g(us)g(to)f(an)-18 b(y)329 b(of)g(the)g(\002rst)e(goal)i (classes.)452 b(In)329 b(step)f(2,)335 b(we)329 b(ha)-24 b(v)-18 b(e)329 b(reached)g(a)g(\002nal)5978 21623 y(state,)413 b(so)391 b(we)h(visit)g(the)f(object)h(we)g(ha)-24 b(v)-18 b(e)392 b(reached.)642 b(In)392 b(step)f(3,)414 b(we)392 b(are)g(at)f(a)h(set)g(of)f(states)5978 23128 y Fq(Q)6853 22688 y Fo(0)7152 23128 y Fs(.)368 b(Some)282 b(of)f(those)h(states)e (represent)h(goal)h(classes)f(that)g(we)h(ha)-24 b(v)-18 b(e)282 b(not)f(yet)h(reached.)369 b(Other)5978 24634 y(states)392 b(are)h(goal)g(classes)f(that)h(we)g(ha)-24 b(v)-18 b(e)393 b(no)-30 b(w)393 b(reached.)645 b(W)-97 b(e)394 b(create)f(the)g(ne)-18 b(xt)393 b(set)f(of)h(goal)5978 26139 y(classes)344 b(by)h(carrying)g(along)g(those)g(that)h(we)f(ha) -24 b(v)-18 b(e)345 b(not)h(yet)f(reached,)356 b(and)346 b(taking)f(a)g(step)g(in)5978 27645 y(the)303 b(automaton)g Fq(S)313 b Fs(for)302 b(those)h(that)g(we)h(ha)-24 b(v)-18 b(e)303 b(reached.)7859 29542 y(W)-97 b(e)378 b(typically)f(start)f (the)h(algorithm)g(with)g(a)g(unique)g(start)f(state)h(and)g(an)g (object)g Fq(o)g Fs(that)5978 31047 y(matches)303 b(that)g(state.)7859 32944 y(As)470 b(before,)512 b(when)471 b(the)f(object)h(graph)f(is)g (ac)-18 b(yclic,)513 b(this)469 b(al)-12 b(w)g(ays)470 b(terminates.)877 b(If)470 b(the)5978 34449 y(object)303 b(graph)g(can)g(be)h(c)-18 b(yclic,)303 b(then)g(we)h(need)f(to)g (carry)g(around)g(a)g(\223seen\224)h(set,)e(as)h(abo)-18 b(v)g(e.)5978 38300 y Ft(6)1328 b(Calculating)333 b Fx(FIRST)5978 40469 y Fs(W)-97 b(e)278 b(de)-30 b(v)-18 b(elop)278 b(a)g(static)g(description)f(of)h(FIRST)f(using)h(a)g(sequence)g(of)f (lemmas.)368 b(This)277 b(allo)-30 b(ws)5978 41975 y(us)302 b(to)h(compute)h(FIRST)e(from)h(the)g(class)f(graph.)376 b(W)-97 b(e)304 b(start)e(with)h(a)g(\002x)-18 b(ed)303 b(class)g(graph)242 b Fq(C)27 b Fs(.)5978 45200 y Ff(Lemma)303 b(1)606 b Fq(Ther)-45 b(e)230 b(e)-24 b(xists)229 b(an)i(object)g(gr) -18 b(aph)229 b(O)i(of)169 b(C)258 b(and)231 b(objects)f(o)34723 45382 y Fm(1)35221 45200 y Fq(,)245 b(o)36375 45382 y Fm(2)37103 45200 y Fq(suc)-18 b(h)230 b(that)h(O)p Fi(\()p Fq(o)43606 45382 y Fm(1)44103 45200 y Fp(;)135 b Fq(o)45181 45382 y Fm(2)45678 45200 y Fi(\))5978 46705 y Fq(if)-22 b(f)303 b Fs(class)o Fi(\()p Fq(o)10703 46887 y Fm(1)11200 46705 y Fi(\))269 b Fh(\024)207 b Fq(C)297 b Fh(\025)268 b Fs(class)p Fi(\()p Fq(o)18840 46887 y Fm(2)19337 46705 y Fi(\))p Fq(.)7859 49931 y Ff(Pr)-22 b(oof:)666 b Fs(The)448 b(forw)-12 b(ard)447 b(direction)h(is)g(immediate)g(from)g(the)g (de\002nition)h(of)e(an)i(object)5978 51436 y(graph)277 b(of)217 b Fq(C)27 b Fs(.)368 b(F)-18 b(or)277 b(the)h(re)-30 b(v)-18 b(erse)277 b(direction,)283 b(construct)277 b(an)h(object)h (graph)e(with)h(tw)-12 b(o)278 b(objects)g Fq(o)45330 51618 y Fm(1)5978 52942 y Fs(and)303 b Fq(o)8637 53124 y Fm(2)9438 52942 y Fs(and)g(the)h(speci\002ed)f(link.)376 b(The)302 b(result)h(is)f(an)h(object)h(graph)f(of)242 b Fq(C)27 b Fs(.)5978 56167 y Ff(Lemma)303 b(2)606 b Fq(Ther)-45 b(e)230 b(e)-24 b(xists)229 b(an)i(object)g(gr)-18 b(aph)229 b(O)i(of)169 b(C)258 b(and)231 b(objects)f(o)34723 56349 y Fm(1)35221 56167 y Fq(,)245 b(o)36375 56349 y Fm(2)37103 56167 y Fq(suc)-18 b(h)230 b(that)h(O)42529 55727 y Fo(\003)43027 56167 y Fi(\()p Fq(o)44104 56349 y Fm(1)44601 56167 y Fp(;)135 b Fq(o)45679 56349 y Fm(2)46176 56167 y Fi(\))5978 57672 y Fq(if)-22 b(f)303 b(cl)62 b(ass)p Fi(\()p Fq(o)10834 57854 y Fm(1)11330 57672 y Fi(\))269 b(\()p Fh(\024)206 b Fq(C)297 b Fh(\025)p Fi(\))16209 57232 y Fo(\003)16975 57672 y Fq(cl)62 b(ass)p Fi(\()p Fq(o)20539 57854 y Fm(2)21035 57672 y Fi(\))303 b Fq(.)7859 60898 y Ff(Pr)-22 b(oof:)537 b Fs(Ag)-6 b(ain,)404 b(the)384 b(forw)-12 b(ard)383 b(direction)h(is)f(immediate.)619 b(F)-18 b(or)383 b(the)h(re)-30 b(v)-18 b(erse,)402 b(apply)384 b(in-)5978 62403 y(duction)364 b(on)g(the)h(standard)e(de\002nition)i (of)f Fi(\()p Fh(\000)p Fi(\))26141 61963 y Fo(\003)27000 62403 y Fs(\(re\003e)-18 b(xi)-30 b(v)-18 b(e)363 b(transiti)-30 b(v)-18 b(e)364 b(closure\),)378 b(using)364 b(the)5978 63908 y(preceding)303 b(lemma.)7859 65805 y(A)h(picture)f(of)f(this)h (situation)g(is)f(sho)-30 b(wn)303 b(in)g(\002gure)g(2.)25600 69672 y(7)p eop %%Page: 8 8 8 7 bop 4181 21087 a @beginspecial 0 @llx 0 @lly 391 @urx 132 @ury 3910 @rwi @setspecial%%BeginDocument: paths.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: paths.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Fri May 31 16:31:53 2002 %%For: wand@alnilam.ccs.neu.edu (Mitchell Wand) %%Orientation: Portrait %%BoundingBox: 0 0 391 132 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 0.6000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -10.0 174.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 5812 m -1000 -1000 l 12123 -1000 l 12123 5812 l cp clip 0.03600 0.03600 sc % Polyline 7.500 slw n 2100 1200 m 2700 1200 l 2700 1800 l 2100 1800 l cp gs col0 s gr % Polyline n 1500 2400 m 2100 2400 l 2100 3000 l 1500 3000 l cp gs col0 s gr % Polyline n 1500 4200 m 2100 4200 l 2100 4800 l 1500 4800 l cp gs col0 s gr % Polyline [15 45] 45 sd gs clippath 1770 3147 m 1800 3027 l 1830 3147 l 1830 2985 l 1770 2985 l cp clip n 1800 4200 m 1800 3000 l gs col0 s gr gr [] 0 sd % arrowhead n 1770 3147 m 1800 3027 l 1830 3147 l 1800 3147 l 1770 3147 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 3903 4470 m 4023 4500 l 3903 4530 l 4065 4530 l 4065 4470 l cp clip n 2100 4500 m 4050 4500 l gs col0 s gr gr % arrowhead n 3903 4470 m 4023 4500 l 3903 4530 l 3903 4500 l 3903 4470 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 3303 1470 m 3423 1500 l 3303 1530 l 3465 1530 l 3465 1470 l cp clip n 2700 1500 m 3450 1500 l gs col0 s gr gr % arrowhead n 3303 1470 m 3423 1500 l 3303 1530 l 3303 1500 l 3303 1470 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 2275 1883 m 2380 1819 l 2317 1925 l 2432 1811 l 2389 1768 l cp clip n 1800 2400 m 2400 1800 l gs col0 s gr gr % arrowhead n 2275 1883 m 2380 1819 l 2317 1925 l 2296 1904 l 2275 1883 l cp gs col7 1.00 shd ef gr col0 s % Polyline n 3450 1200 m 4050 1200 l 4050 1800 l 3450 1800 l cp gs col0 s gr % Polyline n 4050 2400 m 4650 2400 l 4650 3000 l 4050 3000 l cp gs col0 s gr % Polyline n 4050 4200 m 4650 4200 l 4650 4800 l 4050 4800 l cp gs col0 s gr % Polyline [15 45] 45 sd gs clippath 4320 3147 m 4350 3027 l 4380 3147 l 4380 2985 l 4320 2985 l cp clip n 4350 4200 m 4350 3000 l gs col0 s gr gr [] 0 sd % arrowhead n 4320 3147 m 4350 3027 l 4380 3147 l 4350 3147 l 4320 3147 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 3833 1925 m 3769 1819 l 3875 1883 l 3761 1768 l 3718 1811 l cp clip n 4350 2400 m 3750 1800 l gs col0 s gr gr % arrowhead n 3833 1925 m 3769 1819 l 3875 1883 l 3854 1904 l 3833 1925 l cp gs col7 1.00 shd ef gr col0 s % Polyline n 4650 1200 m 5250 1200 l 5250 1800 l 4650 1800 l cp gs col0 s gr % Polyline n 4050 2400 m 4650 2400 l 4650 3000 l 4050 3000 l cp gs col0 s gr % Polyline n 4050 4200 m 4650 4200 l 4650 4800 l 4050 4800 l cp gs col0 s gr % Polyline [15 45] 45 sd gs clippath 4320 3147 m 4350 3027 l 4380 3147 l 4380 2985 l 4320 2985 l cp clip n 4350 4200 m 4350 3000 l gs col0 s gr gr [] 0 sd % arrowhead n 4320 3147 m 4350 3027 l 4380 3147 l 4350 3147 l 4320 3147 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 6453 4470 m 6573 4500 l 6453 4530 l 6615 4530 l 6615 4470 l cp clip n 4650 4500 m 6600 4500 l gs col0 s gr gr % arrowhead n 6453 4470 m 6573 4500 l 6453 4530 l 6453 4500 l 6453 4470 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 5853 1470 m 5973 1500 l 5853 1530 l 6015 1530 l 6015 1470 l cp clip n 5250 1500 m 6000 1500 l gs col0 s gr gr % arrowhead n 5853 1470 m 5973 1500 l 5853 1530 l 5853 1500 l 5853 1470 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 4825 1883 m 4930 1819 l 4867 1925 l 4982 1811 l 4939 1768 l cp clip n 4350 2400 m 4950 1800 l gs col0 s gr gr % arrowhead n 4825 1883 m 4930 1819 l 4867 1925 l 4846 1904 l 4825 1883 l cp gs col7 1.00 shd ef gr col0 s % Polyline n 6000 1200 m 6600 1200 l 6600 1800 l 6000 1800 l cp gs col0 s gr % Polyline n 6600 2400 m 7200 2400 l 7200 3000 l 6600 3000 l cp gs col0 s gr % Polyline n 6600 4200 m 7200 4200 l 7200 4800 l 6600 4800 l cp gs col0 s gr % Polyline [15 45] 45 sd gs clippath 6870 3147 m 6900 3027 l 6930 3147 l 6930 2985 l 6870 2985 l cp clip n 6900 4200 m 6900 3000 l gs col0 s gr gr [] 0 sd % arrowhead n 6870 3147 m 6900 3027 l 6930 3147 l 6900 3147 l 6870 3147 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 6383 1925 m 6319 1819 l 6425 1883 l 6311 1768 l 6268 1811 l cp clip n 6900 2400 m 6300 1800 l gs col0 s gr gr % arrowhead n 6383 1925 m 6319 1819 l 6425 1883 l 6404 1904 l 6383 1925 l cp gs col7 1.00 shd ef gr col0 s % Polyline n 7200 1200 m 7800 1200 l 7800 1800 l 7200 1800 l cp gs col0 s gr % Polyline n 6600 2400 m 7200 2400 l 7200 3000 l 6600 3000 l cp gs col0 s gr % Polyline n 6600 4200 m 7200 4200 l 7200 4800 l 6600 4800 l cp gs col0 s gr % Polyline [15 45] 45 sd gs clippath 6870 3147 m 6900 3027 l 6930 3147 l 6930 2985 l 6870 2985 l cp clip n 6900 4200 m 6900 3000 l gs col0 s gr gr [] 0 sd % arrowhead n 6870 3147 m 6900 3027 l 6930 3147 l 6900 3147 l 6870 3147 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 9003 4470 m 9123 4500 l 9003 4530 l 9165 4530 l 9165 4470 l cp clip n 7200 4500 m 9150 4500 l gs col0 s gr gr % arrowhead n 9003 4470 m 9123 4500 l 9003 4530 l 9003 4500 l 9003 4470 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 8403 1470 m 8523 1500 l 8403 1530 l 8565 1530 l 8565 1470 l cp clip n 7800 1500 m 8550 1500 l gs col0 s gr gr % arrowhead n 8403 1470 m 8523 1500 l 8403 1530 l 8403 1500 l 8403 1470 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 7375 1883 m 7480 1819 l 7417 1925 l 7532 1811 l 7489 1768 l cp clip n 6900 2400 m 7500 1800 l gs col0 s gr gr % arrowhead n 7375 1883 m 7480 1819 l 7417 1925 l 7396 1904 l 7375 1883 l cp gs col7 1.00 shd ef gr col0 s % Polyline n 8550 1200 m 9150 1200 l 9150 1800 l 8550 1800 l cp gs col0 s gr % Polyline n 9150 2400 m 9750 2400 l 9750 3000 l 9150 3000 l cp gs col0 s gr % Polyline n 9150 4200 m 9750 4200 l 9750 4800 l 9150 4800 l cp gs col0 s gr % Polyline [15 45] 45 sd gs clippath 9420 3147 m 9450 3027 l 9480 3147 l 9480 2985 l 9420 2985 l cp clip n 9450 4200 m 9450 3000 l gs col0 s gr gr [] 0 sd % arrowhead n 9420 3147 m 9450 3027 l 9480 3147 l 9450 3147 l 9420 3147 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 8933 1925 m 8869 1819 l 8975 1883 l 8861 1768 l 8818 1811 l cp clip n 9450 2400 m 8850 1800 l gs col0 s gr gr % arrowhead n 8933 1925 m 8869 1819 l 8975 1883 l 8954 1904 l 8933 1925 l cp gs col7 1.00 shd ef gr col0 s % Polyline [60] 0 sd n 300 3600 m 11100 3600 l gs col0 s gr [] 0 sd % Polyline n 1500 2475 m 2100 2475 l gs col0 s gr % Polyline n 2100 1275 m 2700 1275 l gs col0 s gr % Polyline n 3450 1275 m 4050 1275 l gs col0 s gr % Polyline n 4050 2475 m 4650 2475 l gs col0 s gr % Polyline n 4650 1275 m 5250 1275 l gs col0 s gr % Polyline n 6000 1275 m 6600 1275 l gs col0 s gr % Polyline n 6600 2475 m 7200 2475 l gs col0 s gr % Polyline n 7200 1275 m 7800 1275 l gs col0 s gr % Polyline n 8550 1275 m 9150 1275 l gs col0 s gr % Polyline n 9150 2475 m 9750 2475 l gs col0 s gr /Times-Italic ff 180.00 scf sf 300 4575 m gs 1 -1 sc (objects:) col0 sh gr /Times-Italic ff 180.00 scf sf 300 2775 m gs 1 -1 sc (their classes:) col0 sh gr /Times-Italic ff 180.00 scf sf 10200 3300 m gs 1 -1 sc (class graph) col0 sh gr /Times-Italic ff 180.00 scf sf 10200 3975 m gs 1 -1 sc (object graph) col0 sh gr /Times-Italic ff 180.00 scf sf 2925 1425 m gs 1 -1 sc (e1) col0 sh gr /Times-Italic ff 180.00 scf sf 2925 4425 m gs 1 -1 sc (e1) col0 sh gr /Times-Italic ff 180.00 scf sf 5475 1425 m gs 1 -1 sc (e2) col0 sh gr /Times-Italic ff 180.00 scf sf 5475 4425 m gs 1 -1 sc (e2) col0 sh gr /Times-Italic ff 180.00 scf sf 8100 1425 m gs 1 -1 sc (e3) col0 sh gr /Times-Italic ff 180.00 scf sf 8100 4425 m gs 1 -1 sc (e3) col0 sh gr $F2psEnd rs %%EndDocument @endspecial 5978 23699 a Fs(Figure)353 b(2:)476 b(A)353 b(path)h(in)f(an)h(object)f(graph.)527 b(If)352 b(there)i(is)e(a)i (path)f(in)h(the)f(graph)h(from)e Fq(o)42273 23881 y Fm(1)43125 23699 y Fs(to)h Fq(o)45027 23881 y Fm(2)45525 23699 y Fs(,)5978 25205 y(then)303 b Fq(cl)62 b(ass)p Fi(\()p Fq(o)11932 25387 y Fm(1)12428 25205 y Fi(\))269 b(\()p Fh(\024)206 b Fq(C)297 b Fh(\025)p Fi(\))17307 24765 y Fo(\003)18073 25205 y Fq(cl)62 b(ass)p Fi(\()p Fq(o)21637 25387 y Fm(2)22133 25205 y Fi(\))p Fs(.)5978 31470 y Ff(Lemma)303 b(3)606 b Fq(Let)462 b(c)14014 31652 y Fm(1)14974 31470 y Fq(and)g(c)17792 31652 y Fm(2)18753 31470 y Fq(be)g(classes.)851 b(Then)462 b(ther)-45 b(e)462 b(e)-24 b(xists)461 b(an)i(object)f(gr)-18 b(aph)461 b(O)i(of)401 b(C)5978 32976 y(and)393 b(objects)f(o)12621 33158 y Fm(1)13120 32976 y Fq(,)415 b(o)14444 33158 y Fm(2)15335 32976 y Fq(suc)-18 b(h)392 b(that)h Fs(class)p Fi(\()p Fq(o)23644 33158 y Fm(1)24141 32976 y Fi(\))319 b Fh(\024)f Fq(c)26730 33158 y Fm(1)27621 32976 y Fq(and)393 b Fs(class)o Fi(\()p Fq(o)33265 33158 y Fm(2)33763 32976 y Fi(\))318 b Fh(\024)g Fq(c)36351 33158 y Fm(2)37243 32976 y Fq(and)393 b(O)40329 32536 y Fo(\003)40827 32976 y Fi(\()p Fq(o)41904 33158 y Fm(1)42401 32976 y Fp(;)135 b Fq(o)43479 33158 y Fm(2)43976 32976 y Fi(\))392 b Fq(if)-22 b(f)5978 34481 y(c)6516 34663 y Fm(1)7283 34481 y Fh(\025)268 b Fs(class)p Fi(\()p Fq(o)11928 34663 y Fm(1)12425 34481 y Fi(\))h(\()p Fh(\024)206 b Fq(C)297 b Fh(\025)p Fi(\))17304 34041 y Fo(\003)18070 34481 y Fs(class)o Fi(\()p Fq(o)21503 34663 y Fm(2)22001 34481 y Fi(\))268 b Fh(\024)g Fq(c)24489 34663 y Fm(2)24988 34481 y Fq(.)7859 37706 y Ff(Pr)-22 b(oof:)376 b Fs(Immediate.)5978 40932 y Ff(Theor)-22 b(em)303 b(1)14976 42437 y Fs(FIRST)p Fi(\()p Fq(c)p Fp(;)135 b Fq(c)20296 41937 y Fo(0)20592 42437 y Fi(\))269 b(=)f Fh(f)p Fq(e)i Fh(j)e Fq(c)i Fi(\()p Fh(\024)d Fq(e)i Fh(\025)p Fi(\)\()p Fh(\024)205 b Fq(C)297 b Fh(\025)p Fi(\))33410 41937 y Fo(\003)34175 42437 y Fh(\024)269 b Fq(c)35925 41937 y Fo(0)36224 42437 y Fh(g)7859 45662 y Ff(Pr)-22 b(oof:)538 b Fs(W)-97 b(e)385 b(must)f(sho)-30 b(w)384 b(that)h(there)f(e)-18 b(xists)383 b(an)i(object)g(graph)f Fq(O)h Fs(of)323 b Fq(C)412 b Fs(and)385 b(objects)f Fq(o)5978 47168 y Fs(and)303 b Fq(o)8637 46728 y Fo(0)9239 47168 y Fs(such)g(that)7493 50061 y(1.)606 b(class)o Fi(\()p Fq(o)p Fi(\))268 b(=)g Fq(c)7493 52563 y Fs(2.)606 b(class)o Fi(\()p Fq(o)12441 52123 y Fo(0)12739 52563 y Fi(\))269 b Fh(\024)f Fq(c)15228 52123 y Fo(0)7493 55064 y Fs(3.)606 b Fq(o)269 b(eO)11296 54624 y Fo(\003)12064 55064 y Fq(o)12670 54624 y Fo(0)5978 57958 y Fs(if)-30 b(f)302 b Fq(c)269 b Fi(\()p Fh(\024)f Fq(e)h Fh(\025)p Fi(\)\()p Fh(\024)205 b Fq(C)296 b Fh(\025)p Fi(\))16242 57518 y Fo(\003)17008 57958 y Fh(\024)268 b Fq(c)18757 57518 y Fo(0)19056 57958 y Fs(.)7859 59855 y(The)275 b(forw)-12 b(ard)275 b(direction)g(is)f(immediate)i(from)e(the)i (de\002nition)f(of)g(an)g(object)h(graph)f(of)214 b Fq(C)27 b Fs(.)5978 61360 y(F)-18 b(or)302 b(the)h(re)-30 b(v)-18 b(erse)302 b(de\002nition,)h(consider)g(a)g(sequence)h(of)e(classes)g (such)h(that)13033 64762 y Fq(c)p Fi(\()p Fh(\024)267 b Fq(e)j Fh(\025)p Fi(\))p Fq(c)18012 64944 y Fm(1)18508 64762 y Fi(\()p Fh(\024)e Fq(e)20728 64944 y Fm(1)21495 64762 y Fh(\025)p Fi(\))p Fq(c)23447 64944 y Fm(2)23944 64762 y Fi(\()p Fh(\024)f Fq(e)26163 64944 y Fm(2)26931 64762 y Fh(\025)p Fi(\))135 b Fp(:)g(:)g(:)128 b Fi(\()p Fh(\024)267 b Fq(e)32108 64944 y Fe(n)p Fg(+)p Fm(1)34007 64762 y Fh(\025)p Fi(\))p Fq(c)35959 64944 y Fe(n)36725 64762 y Fh(\024)h Fq(c)38474 64262 y Fo(0)25600 69672 y Fs(8)p eop %%Page: 9 9 9 8 bop 7859 7638 a Fs(Then)375 b(construct)f(an)g(object)h(graph)g (with)f Fq(n)195 b Fi(+)g Fs(2)373 b(objects,)392 b(of)374 b(classes)g Fq(c)p Fs(,)392 b Fq(c)40005 7820 y Fm(1)40504 7638 y Fs(,)g(.)182 b(.)g(.)g(,)p Fq(c)43495 7820 y Fe(n)43993 7638 y Fs(,)392 b Fq(c)45226 7198 y Fo(0)45525 7638 y Fs(,)5978 9143 y(with)311 b(a)g(link)g(labelled)h Fq(e)g Fs(from)e(the)h Fq(c)p Fs(-object)h(to)f(the)g Fq(c)28748 9325 y Fm(1)29558 9143 y Fs(object,)j(a)d(link)g(labelled)h Fq(e)40870 9325 y Fm(1)41679 9143 y Fs(from)f(the)5978 10649 y Fq(c)6516 10831 y Fm(1)7379 10649 y Fs(object)365 b(to)g(the)g Fq(c)14398 10831 y Fm(2)15261 10649 y Fs(object,)380 b(etc.)562 b(Let)364 b Fq(o)h Fs(be)g(the)g(\002rst)f(object)h(in)g (this)f(sequence)h(and)g Fq(o)44020 10209 y Fo(0)44684 10649 y Fs(be)5978 12154 y(the)303 b(last.)375 b(This)302 b(object)i(graph)f(satis\002es)e(the)j(requirements.)375 b Ff(QED)7859 14051 y Fs(Similarly)-79 b(,)379 b(to)363 b(\002nd)g(all)h(the)f(edges)h(from)e(an)i(object)g(of)f(class)f Fq(c)i Fs(that)f(might)h(lead)g(to)f(an)5978 15557 y(edge)303 b Fq(e)p Fs(,)g(we)h(compute)12727 18959 y(FIRST)p Fi(\()p Fq(c)p Fp(;)135 b Fq(e)p Fi(\))267 b(=)h Fh(f)p Fq(e)21140 18459 y Fo(0)21708 18959 y Fh(j)g Fi(\()p Fh(9)p Fq(c)23995 18459 y Fo(0)24293 18959 y Fi(\)\()p Fq(c)g Fi(\()p Fh(\024)g Fq(e)28261 18459 y Fo(0)28829 18959 y Fh(\025)p Fi(\)\()p Fh(\024)205 b Fq(C)297 b Fh(\025)p Fi(\))34381 18459 y Fo(\003)35146 18959 y Fh(\024)268 b Fq(e)i(c)37703 18459 y Fo(0)38002 18959 y Fi(\))p Fh(g)5978 22797 y Ft(7)1328 b(A)332 b(Simple)f(Example)5978 24967 y Fs(W)-97 b(e)266 b(illustrate)f(automated)i(tra)-24 b(v)-18 b(ersal)264 b(generation)j(with)f(a)g(simple)f(e)-18 b(xample,)274 b(written)266 b(in)g(Ja)-24 b(v)-30 b(a)5978 26472 y(using)302 b(the)h(DJ)g(library)-79 b(.)7859 28369 y(Consider)330 b(an)h(equation)f(system)f(that)h(contains)g(equations)g(with)g(a)g (left-hand)g(side)g(and)5978 29875 y(a)303 b(right-hand)f(side.)376 b(A)303 b(typical)g(set)g(of)g(equations)g(might)g(be)5978 33026 y Fl(X1)637 b(=)f(\(X2)i(+)f(X3\))5978 34531 y(X2)g(=)f(\(X5)i(+) f(\(X3)g(*)g(X1\)\))5978 36037 y(X3)g(=)f(\(X5)i(+)f(\(7)g(*)f(5\)\)) 7859 39188 y Fs(A)382 b(possible)e(class)g(diagram)h(for)g(these)f (structures)g(is)h(sho)-30 b(wn)380 b(in)h(Figure)g(3,)401 b(using)380 b(no-)5978 40693 y(tation)361 b(similar)f(to)g(that)h(of)g (our)f(pre)-30 b(vious)360 b(\002gures.)549 b(The)360 b(asterisks)g(indicate)h(one-man)-18 b(y)361 b(re-)5978 42199 y(lations;)339 b(the)-18 b(y)328 b(are)f(included)h(for)f(UML)g (compatibility)h(b)-24 b(ut)328 b(are)f(not)h(part)f(of)h(our)f(model;) 340 b(in)5978 43704 y(our)302 b(model)i(has-as-part)d(relations)i(are)g (al)-12 b(w)g(ays)302 b(possibly)h(one-man)-18 b(y)-79 b(.)7859 45601 y(In)303 b(DJ,)g(we)g(search)g(for)f(all)h(minimal)h Fi(\()p Fq(c)24825 45783 y Fm(1)25322 45601 y Fp(;)135 b(:)g(:)g(:)129 b(;)135 b Fq(c)28214 45783 y Fe(K)28907 45601 y Fi(\))p Fs(-paths)302 b(using)h(the)g(search)f(criterion)5978 48433 y Fl(through)638 b Fq(c)11606 48615 y Fm(1)12741 48433 y Fl(through)h Fq(c)18370 48615 y Fm(2)19505 48433 y Fl(...)e(to)g Fq(c)24497 48615 y Fe(K)5978 51264 y Fs(DJ)302 b(tra)-24 b(v)-18 b(ersal)302 b(speci\002cations)h(allo)-30 b(w)303 b(se)-30 b(v)-18 b(eral)302 b(e)-18 b(xtensions)302 b(of)h(this)g(notation.)376 b(The)303 b(criterion)5978 54096 y Fl(from)637 b Fq(c)9697 54278 y Fm(0)10832 54096 y Fl(through)i Fq(c)16461 54278 y Fm(1)17596 54096 y Fl(through)f Fq(c)23224 54278 y Fm(2)24359 54096 y Fl(...)f(to)h Fq(c)29352 54278 y Fe(K)5978 56927 y Fs(has)393 b(the)g(same)g(beha)-24 b(vior)394 b(as)f(the)g(search)g(abo)-18 b(v)g(e,)417 b(b)-24 b(ut)393 b(f)-12 b(ails)392 b(if)h(its)g(starting)g(point)g(is) g(not)g(of)5978 58432 y(type)377 b Fq(c)8980 58614 y Fm(0)9478 58432 y Fs(.)598 b(DJ)376 b(also)h(allo)-30 b(ws)376 b(edge)i(speci\002cations)f(of)f(the)h(form)g Fl(through)639 b Fq(e)p Fs(.)597 b(This)377 b(can)g(be)5978 59938 y(implemented)247 b(by)h(e)-18 b(xtending)248 b(FIRST)o Fi(\()p Fq(c)23333 60120 y Fm(1)23831 59938 y Fp(;)135 b Fq(c)24841 60120 y Fm(2)25337 59938 y Fi(\))247 b Fs(to)g(FIRST)p Fi(\()p Fq(c)p Fp(;)135 b Fq(e)p Fi(\))244 b Fs(as)j(de\002ned)h(in)f (section)h(6)f(and)5978 61443 y(modifying)302 b(the)i(algorithm)f(in)g (section)g(5)g(correspondingly)-79 b(.)7859 63340 y(A)265 b(a)f(DJ)g(tra)-24 b(v)-18 b(ersal)263 b(speci\002cation)h(may)h (include)f(a)h(clause)f Fl(bypassing)640 b Fq(c)39380 63522 y Fm(1)40779 63340 y Fs(specifying)5978 64846 y(that)399 b(the)g(portion)f(of)h(the)g(path)g(in)g(which)g(this)g(clause)f (occurs)h(may)g(not)g(pass)f(through)h(an)5978 66351 y(object)282 b(of)g(class)g Fq(c)13691 66533 y Fm(1)14189 66351 y Fs(.)369 b(The)282 b(DJ)g(library)f(also)h(includes)g(w)-12 b(ays)282 b(to)h(specify)f(strate)-18 b(gy)281 b(graphs)h([9)o(].)25600 69672 y(9)p eop %%Page: 10 10 10 9 bop 10241 30420 a @beginspecial 0 @llx 0 @lly 385 @urx 295 @ury 2160 @rhi @setspecial%%BeginDocument: figs/equations.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: equations.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Fri Dec 28 11:40:52 2001 %%For: wand@alnilam.ccs.neu.edu (Mitchell Wand) %%Orientation: Portrait %%BoundingBox: 0 0 385 295 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -228.0 384.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 7387 m -1000 -1000 l 11212 -1000 l 11212 7387 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 6675 6075 m 7725 6075 l 7725 6375 l 6675 6375 l cp gs col0 s gr /Courier-Bold ff 180.00 scf sf 6750 6300 m gs 1 -1 sc (Operator) col0 sh gr % Polyline n 7950 6075 m 9675 6075 l 9675 6375 l 7950 6375 l cp gs col0 s gr /Courier-Bold ff 180.00 scf sf 7950 6300 m gs 1 -1 sc (Expression_List) col0 sh gr % Polyline n 5475 6075 m 6450 6075 l 6450 6375 l 5475 6375 l cp gs col0 s gr /Courier-Bold ff 180.00 scf sf 5475 6300 m gs 1 -1 sc (Numerical) col0 sh gr % Polyline n 4350 1500 m 6150 1500 l 6150 1800 l 4350 1800 l cp gs col0 s gr % Polyline n 4425 2400 m 6000 2400 l 6000 2700 l 4425 2700 l cp gs col0 s gr % Polyline n 4650 3300 m 5775 3300 l 5775 3675 l 4650 3675 l cp gs col0 s gr % Polyline n 3825 4275 m 4875 4275 l 4875 4575 l 3825 4575 l cp gs col0 s gr % Polyline n 5700 4275 m 6825 4275 l 6825 4575 l 5700 4575 l cp gs col0 s gr % Polyline n 3825 5175 m 4500 5175 l 4500 5475 l 3825 5475 l cp gs col0 s gr % Polyline n 5625 5175 m 6375 5175 l 6375 5475 l 5625 5475 l cp gs col0 s gr % Polyline n 6825 5175 m 7800 5175 l 7800 5475 l 6825 5475 l cp gs col0 s gr % Polyline gs clippath 5205 2253 m 5175 2373 l 5145 2253 l 5145 2415 l 5205 2415 l cp clip n 5175 1800 m 5175 2400 l gs col0 s gr gr % arrowhead n 5205 2253 m 5175 2373 l 5145 2253 l 5175 2253 l 5205 2253 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 5205 3153 m 5175 3273 l 5145 3153 l 5145 3315 l 5205 3315 l cp clip n 5175 2700 m 5175 3300 l gs col0 s gr gr % arrowhead n 5205 3153 m 5175 3273 l 5145 3153 l 5175 3153 l 5205 3153 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 4487 4213 m 4371 4259 l 4451 4164 l 4320 4260 l 4356 4308 l cp clip n 5175 3675 m 4350 4275 l gs col0 s gr gr % arrowhead n 4487 4213 m 4371 4259 l 4451 4164 l 4469 4189 l 4487 4213 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 6184 4179 m 6276 4262 l 6156 4232 l 6299 4309 l 6327 4256 l cp clip n 5175 3675 m 6300 4275 l gs col0 s gr gr % arrowhead n 6184 4179 m 6276 4262 l 6156 4232 l 6170 4206 l 6184 4179 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 5970 4722 m 6000 4602 l 6030 4722 l 6030 4560 l 5970 4560 l cp clip n 6000 5175 m 6000 4575 l gs col0 s gr gr % arrowhead n 5970 4722 m 6000 4602 l 6030 4722 l 6000 4722 l 5970 4722 l cp gs col7 1.00 shd ef gr col0 s % Polyline gs clippath 6690 4695 m 6620 4592 l 6730 4650 l 6609 4543 l 6569 4587 l cp clip n 7275 5175 m 6600 4575 l gs col0 s gr gr % arrowhead n 6690 4695 m 6620 4592 l 6730 4650 l 6710 4673 l 6690 4695 l cp gs col7 1.00 shd ef gr col0 s % Polyline gs clippath 4230 5028 m 4200 5148 l 4170 5028 l 4170 5190 l 4230 5190 l cp clip n 4200 4575 m 4200 5175 l gs col0 s gr gr % arrowhead n 4230 5028 m 4200 5148 l 4170 5028 l 4200 5028 l 4230 5028 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 7003 5966 m 6914 6052 l 6952 5934 l 6867 6072 l 6917 6104 l cp clip n 7275 5475 m 6900 6075 l gs col0 s gr gr % arrowhead n 7003 5966 m 6914 6052 l 6952 5934 l 6978 5950 l 7003 5966 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 8212 5976 m 8301 6061 l 8182 6028 l 8323 6108 l 8353 6056 l cp clip n 7275 5475 m 8325 6075 l gs col0 s gr gr % arrowhead n 8212 5976 m 8301 6061 l 8182 6028 l 8197 6002 l 8212 5976 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 5970 5622 m 6000 5502 l 6030 5622 l 6030 5460 l 5970 5460 l cp clip n 6000 6075 m 6000 5475 l gs col0 s gr gr % arrowhead n 5970 5622 m 6000 5502 l 6030 5622 l 6000 5622 l 5970 5622 l cp gs col7 1.00 shd ef gr col0 s % Polyline gs clippath 5815 5621 m 5849 5501 l 5875 5623 l 5880 5461 l 5821 5459 l cp clip n 4650 4275 m 4653 4273 l 4659 4269 l 4670 4262 l 4686 4251 l 4706 4238 l 4731 4223 l 4757 4207 l 4785 4191 l 4813 4177 l 4841 4164 l 4867 4153 l 4891 4145 l 4913 4139 l 4934 4136 l 4954 4136 l 4973 4138 l 4990 4144 l 5008 4152 l 5025 4163 l 5038 4173 l 5052 4184 l 5065 4197 l 5078 4212 l 5092 4228 l 5106 4246 l 5120 4266 l 5134 4287 l 5148 4310 l 5162 4334 l 5176 4359 l 5190 4386 l 5204 4413 l 5217 4442 l 5230 4471 l 5243 4501 l 5255 4531 l 5266 4562 l 5277 4592 l 5288 4622 l 5298 4653 l 5307 4683 l 5315 4712 l 5323 4742 l 5331 4771 l 5338 4800 l 5344 4829 l 5350 4858 l 5355 4888 l 5361 4918 l 5366 4948 l 5370 4979 l 5375 5010 l 5379 5041 l 5383 5073 l 5387 5104 l 5391 5136 l 5395 5167 l 5398 5199 l 5402 5229 l 5405 5259 l 5409 5289 l 5412 5317 l 5416 5345 l 5420 5371 l 5423 5396 l 5427 5421 l 5431 5444 l 5436 5465 l 5440 5486 l 5445 5506 l 5450 5525 l 5457 5548 l 5465 5571 l 5474 5592 l 5483 5613 l 5493 5632 l 5504 5651 l 5516 5669 l 5528 5685 l 5541 5701 l 5553 5715 l 5567 5728 l 5580 5740 l 5593 5750 l 5606 5759 l 5618 5767 l 5630 5773 l 5642 5778 l 5654 5782 l 5665 5785 l 5675 5788 l 5688 5789 l 5700 5789 l 5712 5788 l 5724 5786 l 5736 5782 l 5747 5778 l 5758 5772 l 5768 5765 l 5778 5757 l 5787 5748 l 5795 5739 l 5803 5729 l 5809 5719 l 5815 5709 l 5820 5698 l 5825 5688 l 5830 5675 l 5833 5662 l 5837 5647 l 5840 5631 l 5842 5613 l 5844 5593 l 5846 5571 l 5847 5548 l 5848 5525 l 5849 5504 l 5850 5475 l gs col0 s gr gr % arrowhead n 5815 5621 m 5849 5501 l 5875 5623 l 5845 5622 l 5815 5621 l cp gs col7 1.00 shd ef gr col0 s % Polyline gs clippath 6972 4455 m 6852 4425 l 6972 4395 l 6810 4395 l 6810 4455 l cp clip n 9675 6225 m 9678 6225 l 9684 6224 l 9696 6223 l 9712 6222 l 9734 6219 l 9761 6216 l 9791 6211 l 9823 6206 l 9856 6200 l 9889 6193 l 9920 6185 l 9949 6176 l 9975 6166 l 10000 6155 l 10022 6143 l 10041 6130 l 10059 6115 l 10074 6098 l 10088 6080 l 10101 6060 l 10113 6038 l 10121 6018 l 10129 5998 l 10136 5976 l 10143 5953 l 10149 5928 l 10155 5902 l 10160 5874 l 10166 5845 l 10170 5815 l 10175 5783 l 10178 5750 l 10182 5717 l 10185 5682 l 10188 5647 l 10190 5611 l 10192 5575 l 10194 5539 l 10196 5503 l 10197 5468 l 10198 5433 l 10199 5398 l 10199 5364 l 10199 5331 l 10200 5298 l 10200 5266 l 10200 5235 l 10200 5205 l 10200 5175 l 10200 5141 l 10200 5107 l 10200 5074 l 10199 5041 l 10199 5008 l 10197 4975 l 10196 4943 l 10194 4911 l 10191 4879 l 10188 4848 l 10184 4818 l 10179 4788 l 10174 4760 l 10167 4733 l 10160 4707 l 10151 4682 l 10142 4659 l 10132 4637 l 10121 4617 l 10109 4599 l 10096 4581 l 10082 4566 l 10067 4551 l 10050 4538 l 10036 4528 l 10021 4518 l 10004 4509 l 9987 4501 l 9968 4493 l 9947 4486 l 9926 4479 l 9902 4473 l 9877 4467 l 9850 4461 l 9822 4456 l 9792 4452 l 9761 4448 l 9727 4444 l 9693 4441 l 9657 4438 l 9619 4435 l 9580 4433 l 9541 4431 l 9499 4430 l 9457 4428 l 9414 4427 l 9370 4427 l 9326 4426 l 9280 4426 l 9234 4425 l 9186 4425 l 9138 4425 l 9088 4425 l 9038 4425 l 9004 4425 l 8969 4425 l 8933 4425 l 8897 4425 l 8859 4425 l 8820 4425 l 8780 4425 l 8738 4425 l 8694 4425 l 8649 4425 l 8602 4425 l 8553 4425 l 8501 4425 l 8447 4425 l 8391 4425 l 8333 4425 l 8272 4425 l 8209 4425 l 8143 4425 l 8075 4425 l 8005 4425 l 7932 4425 l 7858 4425 l 7783 4425 l 7707 4425 l 7630 4425 l 7554 4425 l 7478 4425 l 7404 4425 l 7332 4425 l 7263 4425 l 7197 4425 l 7136 4425 l 7080 4425 l 7029 4425 l 6984 4425 l 6945 4425 l 6912 4425 l 6885 4425 l 6864 4425 l 6848 4425 l 6825 4425 l gs col0 s gr gr % arrowhead n 6972 4455 m 6852 4425 l 6972 4395 l 6972 4425 l 6972 4455 l cp gs 0.00 setgray ef gr col0 s /Courier-Bold ff 180.00 scf sf 4500 1725 m gs 1 -1 sc (EquationSystem) col0 sh gr /Courier-Bold ff 180.00 scf sf 4500 2625 m gs 1 -1 sc (Equation_List) col0 sh gr /Courier-Bold ff 180.00 scf sf 4800 3600 m gs 1 -1 sc (Equation) col0 sh gr /Courier-Bold ff 180.00 scf sf 3900 4500 m gs 1 -1 sc (Variable) col0 sh gr /Courier-Bold ff 180.00 scf sf 5700 4500 m gs 1 -1 sc (Expression) col0 sh gr /Courier-Bold ff 180.00 scf sf 3900 5400 m gs 1 -1 sc (Ident) col0 sh gr /Courier-Bold ff 180.00 scf sf 5700 5400 m gs 1 -1 sc (Simple) col0 sh gr /Courier-Bold ff 180.00 scf sf 6900 5400 m gs 1 -1 sc (Compound) col0 sh gr /Courier-Bold ff 180.00 scf sf 5325 2175 m gs 1 -1 sc (equations) col0 sh gr /Courier-Bold ff 180.00 scf sf 4200 4050 m gs 1 -1 sc (lhs) col0 sh gr /Courier-Bold ff 180.00 scf sf 6000 3975 m gs 1 -1 sc (rhs) col0 sh gr /Courier-Bold ff 180.00 scf sf 6750 5775 m gs 1 -1 sc (op) col0 sh gr /Courier-Bold ff 180.00 scf sf 8025 5775 m gs 1 -1 sc (args) col0 sh gr /Courier-Bold ff 180.00 scf sf 6975 4350 m gs 1 -1 sc (*) col0 sh gr /Courier-Bold ff 180.00 scf sf 5250 3225 m gs 1 -1 sc (*) col0 sh gr $F2psEnd rs %%EndDocument @endspecial 15049 33033 a Fs(Figure)303 b(3:)376 b(Class)302 b(graph)h(for)g Fl(EquationSystem)p Fs(.)7859 36734 y(In)414 b(our)f(e)-18 b(xample,)442 b(let)414 b(us)f(say)g(that)h(a)g(v)-30 b(ariable)413 b(is)g Fq(de\002ned)447 b Fs(if)413 b(it)h(appears)f(on)h (the)g(left-)5978 38239 y(hand)357 b(side)g(of)g(an)h(equation)f(and)h (that)f(it)g(is)g Fq(used)390 b Fs(if)357 b(it)g(appears)g(on)g(the)h (right-hand.)538 b(In)357 b(the)5978 39745 y(e)-18 b(xample,)268 b(v)-30 b(ariables)258 b Fl(X1)p Fs(,)269 b Fl(X2)259 b Fs(and)g Fl(X3)h Fs(are)f(de\002ned,)268 b(and)259 b(v)-30 b(ariables)259 b Fl(X2)p Fs(,)268 b Fl(X3)260 b Fs(and)f Fl(X5)g Fs(are)g(used.)5978 41250 y(The)302 b(purpose)h(of)g(our)g(Ja)-24 b(v)-30 b(a)302 b(program)h(is)f(to)h (collect)h(the)f(de\002ned)g(and)h(used)e(v)-30 b(ariables.)7859 43147 y(T)-97 b(o)398 b(solv)-18 b(e)397 b(this)g(problem,)421 b(we)398 b(identify)f(tw)-12 b(o)397 b(tra)-24 b(v)-18 b(ersals.)658 b(The)397 b(\002rst)g(tra)-24 b(v)-18 b(ersal)396 b(may)i(be)5978 44652 y(written)503 b(as)h Fl(from)638 b(EquationSystem)j(through)e(rhs)e(to)g(Variable)p Fs(.)981 b(The)504 b(second)5978 46158 y(may)303 b(be)g(written)g(as)g Fl(from)638 b(Equation)h(System)f(through)h(lhs)f(to)f(Variable)p Fs(.)7859 48055 y(There)375 b(are)h(of)f(course)g(man)-18 b(y)375 b(w)-12 b(ays)375 b(of)g(specifying)g(the)h(same)f(tra)-24 b(v)-18 b(ersals.)591 b(F)-18 b(or)375 b(e)-18 b(xam-)5978 49560 y(ple)450 b(the)h(\002rst)e(could)i(ha)-24 b(v)-18 b(e)451 b(been)g(written)f(as)g Fl(from)638 b(EquationSystem)j(through) e(rhs)5978 51066 y(through)f(Expression)i(to)d(Variable)p Fs(,)282 b(and)273 b(the)g(second)g(could)g(ha)-24 b(v)-18 b(e)273 b(been)g(written)f(as)5978 52571 y Fl(from)637 b(EquationSystem)642 b(bypassing)d(Expression)h(to)d(Variable)p Fs(.)7859 54468 y(The)254 b(DJ)f(library)f(uses)h(re\003ection)g(to)h (compute)g(the)f(rele)-30 b(v)g(ant)253 b(FIRST)g(sets.)359 b(This)252 b(has)h(tw)-12 b(o)5978 55974 y(adv)-30 b(antages:)543 b(\002rst,)406 b(it)387 b(allo)-30 b(ws)386 b(the)h(same)f(code)h(to)g (be)g(reused)f(e)-30 b(v)-18 b(en)387 b(if)f(the)h(class)f(structure) 5978 57479 y(changes.)701 b(Second,)439 b(it)411 b(allo)-30 b(ws)411 b(the)h(system)f(to)g(be)h(implemented)g(as)f(a)g(pure)h(Ja) -24 b(v)-30 b(a)411 b(library)5978 58984 y(rather)302 b(than)i(as)e(a)h(preprocessor)-67 b(.)375 b(This)302 b(is)h(an)g(e)-18 b(xample)304 b(of)e Fq(adaptive)i Fs(beha)-24 b(vior)303 b([8)o(].)7859 60881 y(The)340 b(code)h(for)e(this)g(task)h (is)f(sho)-30 b(wn)339 b(in)h(\002gure)g(4.)487 b(The)339 b(static)h(member)g Fl(cg)h Fs(is)e(bound)h(to)5978 62387 y(a)333 b Fl(ClassGraph)338 b Fs(object)c(that)g(contains)f(a)h (representation)f(of)h(the)g(current)f(class)g(diagram)45027 61947 y Fm(1)45525 62387 y Fs(.)5978 63892 y(The)355 b(method)h Fl(collectVars)k Fs(tak)-12 b(es)355 b(a)h(string)f Fl(travspec)k Fs(that)c(speci\002es)h(the)g(tra)-24 b(v)-18 b(ersal)354 b(to)p 5978 64711 15940 45 v 7328 65528 a Fj(1)7771 65889 y Fv(In)249 b(a)g(real)h(application,)g(this)f(w)-10 b(ould)250 b(probably)f(done)h(globally)g(rather)f(than)h(on)f(a)h(per) -20 b(-class)248 b(basis.)25297 69672 y Fs(10)p eop %%Page: 11 11 11 10 bop 5978 19393 a Fa(class)581 b(EquationSystem{)7140 20721 y(static)h(ClassGraph)h(cg)e(=)g(new)h(ClassGraph\(\);)7140 22049 y(//)f(constructors)i(omitted)f(...)7140 23378 y(HashSet)g(collectVars\(String)i(travspec\){)8302 24706 y(Visitor)e(v)g(=)f(new)h(Visitor\(\){)9464 26034 y(HashSet)h (return_val)f(=)g(new)f(HashSet\(\);)9464 27363 y(void)h (before\(Variable)i(v1\){return_val.add\(v1\);})9464 28691 y(public)f(Object)f(getReturnValue\(\){return)i(return_val;})8302 30019 y(};)8302 31348 y(cg.traverse\(this,)g(travspec,)e(v\);)8302 32676 y(return)g(\(HashSet\)v.getReturnValue\(\);)7140 34004 y(})7140 35333 y(HashSet)g(getUsedVars\(\))h({)8302 36661 y(return)f(this.collectVars)8883 37989 y(\("from)g (EquationSystem)i(through)e(Expression")10046 39318 y(+)f("through)h (rhs)g(to)f(Variable"\);)7140 40646 y(})7140 41974 y(HashSet)h (getDefinedVars\(\))i({)8302 43303 y(return)e(this.collectVars)8883 44631 y(\("from)g(EquationSystem)i(bypassing)e(Expression")9464 45960 y(+)g("to)f(Variable"\);)8302 47288 y(})5978 48616 y(})12987 53885 y Fs(Figure)303 b(4:)375 b(Finding)303 b(the)h(v)-30 b(ariables)302 b(in)h(an)g(equation)h(system)25297 69672 y(11)p eop %%Page: 12 12 12 11 bop 5978 7638 a Fs(be)417 b(performed.)716 b(It)416 b(\002rst)g(creates)g(a)h(visitor)f Fl(v)h Fs(to)g(implement)g(the)g (beha)-24 b(vior)416 b(that)h(is)f(to)h(be)5978 9143 y(performed)448 b(during)g(the)h(tra)-24 b(v)-18 b(ersal.)812 b(Once)449 b(the)g(visitor)f(is)g(created,)485 b Fl(collectVars)453 b Fs(then)5978 10649 y(initiates)235 b(the)h(tra)-24 b(v)-18 b(ersal)234 b(by)i(calling)g(the)g Fl(traverse)j Fs(method)d(of)f(the)h(current)g(class)f(graph)g Fl(cg)p Fs(,)5978 12154 y(passing)305 b(as)i(ar)-22 b(guments)306 b(the)h(object)g(at)f(which)h(to)g(start)e(the)i(tra)-24 b(v)-18 b(ersal)305 b(\()p Fl(this)p Fs(\),)k(the)d(tra)-24 b(v)-18 b(ersal)5978 13660 y(to)303 b(be)g(performed)f(\()p Fl(travspec)p Fs(\),)k(and)d(the)g(visitor)f(to)h(be)h(e)-18 b(x)g(ecuted)303 b(along)g(the)h(w)-12 b(ay)303 b(\()p Fl(v)p Fs(\).)7859 15557 y(The)521 b(e)-18 b(x)g(ecution)520 b(of)g Fl(cg.traverse\(this,)643 b(travspec,)c(v\))521 b Fs(follo)-30 b(ws)520 b(the)g(visitor)5978 17062 y(pattern)434 b([4)o(],)467 b(augmented)435 b(by)f(re\003ection.)770 b(Ev)-18 b(ery)433 b(time)i(the)f(tra)-24 b(v)-18 b(ersal)433 b(reaches)h(a)h(node)f Fq(n)5978 18568 y Fs(for)285 b(which)i(a)f Fl(before)j Fs(method)d(has)g(been)h(de\002ned,)j(it)c(calls)g Fl(v.before\()p Fq(n)p Fl(\))p Fs(.)374 b(The)286 b(tra)-24 b(v)-18 b(ersal)5978 20073 y(algorithm)394 b(uses)g(re\003ection)g(to)g (call)h(the)g Fl(before)h Fs(method)f(only)g(on)f(objects)g(for)g (which)h(a)5978 21579 y Fl(before)355 b Fs(method)e(has)g(been)h (de\002ned.)527 b(Thus,)364 b(when)354 b(the)f(node)h(is)f(a)g(v)-30 b(ariable,)365 b(the)354 b(method)5978 23084 y Fl(before\(Variable)641 b(v1\))408 b Fs(\(the)f(\223visitor)f(method\224\))h(is)f(called,)433 b(adding)407 b(the)g(node)g(to)g(the)5978 24590 y(set.)351 b(Similarly)-79 b(,)245 b(on)230 b(completion)h(of)f(the)g(search,)245 b(the)230 b(tra)-24 b(v)-18 b(ersal)229 b(calls)i Fl (v.getReturnValue\(\))p Fs(,)5978 26095 y(which)303 b(returns)f(the)h (collected)h(hash)f(set.)7859 27992 y(The)472 b(DJ)f(library)g (includes)h(a)g(po)-30 b(werful)471 b(language)h(of)g(tra)-24 b(v)-18 b(ersal)470 b(speci\002cations)i(and)5978 29497 y(methods,)334 b(including)329 b(the)f(possibility)f(of)h(precomputing) h(the)f(FIRST)g(sets,)334 b(and)328 b(of)g(attach-)5978 31003 y(ing)359 b(methods)g(to)g(edge)g(tra)-24 b(v)-18 b(ersals;)385 b(see)359 b([1].)543 b(An)360 b(introduction)f(to)g(DJ,)f (with)i(emphasis)e(on)5978 32508 y(its)302 b(re\003ecti)-30 b(v)-18 b(e)303 b(properties,)f(may)h(be)h(found)f(in)g([13)o(].)5978 36359 y Ft(8)1328 b(Related)332 b(W)-100 b(ork)5978 38528 y Fs(The)345 b Fq(V)-90 b(isitor)345 b Fs(design)g(pattern)h(is)f (discussed)g(in)h(man)-18 b(y)345 b(softw)-12 b(are-engineering)345 b(w)-12 b(orks)345 b(\(e.g.,)5978 40034 y([4)o(]\).)429 b(In)321 b(contrast)f(with)h(the)h(ordinary)e(visitor)g(pattern,)326 b(no)321 b(preparation)g(in)g(the)g(underlying)5978 41539 y(objects)302 b(is)h(necessary)f(in)i(order)e(to)h(use)g(the)g(DJ)g (library)-79 b(.)7859 43436 y(The)443 b(concept)h(of)e(automated)h(tra) -24 b(v)-18 b(ersal)442 b(generation)h(using)g(succinct)g (representation)5978 44941 y(w)-12 b(as)366 b(introduced)h(in)g([7].) 567 b(It)366 b(w)-12 b(as)367 b(formalized)g(in)g([14)o(])g(and)g(is)f (e)-18 b(xtensi)-30 b(v)-18 b(ely)367 b(treated)g(in)g([8)o(],)5978 46447 y(where)325 b(it)f(is)g(the)h(k)-12 b(e)-18 b(y)325 b(idea)g(of)g(Adapti)-30 b(v)-18 b(e)325 b(Programming)f(\(AP\),)g(and) h(is)f(used)h(to)g(implement)5978 47952 y(the)303 b(Adapti)-30 b(v)-18 b(e)303 b(V)-73 b(isitor)302 b(pattern)i([8)o(,)f(pages)g (426\226427].)7859 49849 y(Our)308 b(most)e(comple)-18 b(x)308 b(language)g(of)f(tra)-24 b(v)-18 b(ersal)306 b(speci\002cations,)i(called)g Fq(str)-18 b(ate)-48 b(gy)306 b(gr)-18 b(aphs)p Fs(,)5978 51355 y(is)299 b(introduced)h(in)g([9)o(])g (together)f(with)h(an)g(ef)-30 b(\002cient)300 b(implementation.)375 b(This)299 b(paper)h(pro)-18 b(vides)5978 52860 y(a)246 b(self-contained)g(description)h(of)f(the)h(semantics)f(and)h (algorithms)e(for)h(Adapti)-30 b(v)-18 b(e)247 b(Program-)5978 54366 y(ming)334 b(in)g(a)g(fe)-30 b(w)334 b(pages.)468 b(Instead)334 b(of)g(refering)f(to)h(paths)g(in)g(the)g(class)f (diagram)h(as)g([9])f(does,)5978 55871 y(the)285 b(basic)h(meaning)f (is)g(de\002ned)h(directly)g(in)f(terms)g(of)g(object)h(graphs.)369 b(By)286 b(dealing)g(directly)5978 57377 y(with)412 b(the)h(search)g (algorithm)f(in)h(the)f(object)h(graph,)441 b(it)412 b(a)-24 b(v)g(oids)412 b(the)h(complications)g(of)f(the)5978 58882 y(tra)-24 b(v)-18 b(ersal)301 b(histories)h(of)h([14].)7859 60779 y(Our)231 b(use)f(of)g(the)g(visitor)g(pattern)g(may)g(be)h(re) -18 b(g)-6 b(arded)230 b(as)g(an)g(e)-18 b(xample)231 b(of)f(Aspect-Oriented)5978 62284 y(Programming)466 b([2)o(].)866 b(Aspect-oriented)466 b(programming)g(systems)f(typically)i(consist)f (of)g(a)5978 63790 y(frame)-30 b(w)-12 b(ork)393 b(that)h(identi\002es) g(a)g(set)g(of)g(e)-30 b(v)-18 b(ents)394 b(during)g(the)g(computation) h(at)f(which)g(proce-)5978 65295 y(dures)322 b(may)h(be)g(in)-48 b(v)-24 b(ok)-12 b(ed)322 b(\(the)h(join)g(points\),)k(a)c(declarati) -30 b(v)-18 b(e)322 b(language)i(for)e(specifying)h(a)g(set)25297 69672 y(12)p eop %%Page: 13 13 13 12 bop 5978 7638 a Fs(of)292 b(such)g(e)-30 b(v)-18 b(ents)292 b(\(the)g(\224point)h(cut)g(descriptors\224\),)g(and)f(a)h (means)f(of)h(associating)f(procedures)5978 9143 y(with)400 b(such)g(declarati)-30 b(v)-18 b(ely-speci\002ed)400 b(sets.)667 b(In)400 b(DJ,)g(computation)h(is)f(the)h(tra)-24 b(v)-18 b(ersal,)423 b(and)401 b(a)5978 10649 y(join)336 b(point)h(is)f(the)g(passage)g(of)h(the)f(tra)-24 b(v)-18 b(ersal)336 b(through)g(a)h(node)f(of)h(the)f(object)h(graph.)476 b(Each)5978 12154 y(visitor)344 b(method)i(has)f(a)g(signature)g(that)h (plays)f(the)g(role)g(of)g(a)h(point)f(cut)h(descriptor)-48 b(,)354 b(a)346 b(body)5978 13660 y(that)303 b(plays)g(the)g(role)g(of) f(the)i(associated)e(procedure.)7859 15557 y(In)331 b(the)h(conte)-18 b(xt)331 b(of)g Fq(object-oriented)g(databases)p Fs(,)338 b(tra)-24 b(v)-18 b(ersals)329 b(are)j(hea)-24 b(vily)331 b(used.)460 b(Some)5978 17062 y(automation)281 b(of)g(tra)-24 b(v)-18 b(ersals)280 b(w)-12 b(as)281 b(suggested)g(in)g([12,)g(15,)g (10,)h(6,)f(5].)368 b(Roughly)282 b(speaking,)k(the)5978 18568 y(idea)336 b(in)g(these)g(papers)f(is)h(to)g(tra)-24 b(v)-18 b(erse)335 b(to)h(a)g(tar)-22 b(get)336 b(without)g(specifying) g(the)g(full)g(path)g(lead-)5978 20073 y(ing)354 b(to)h(it.)530 b(Most)354 b(of)g(this)g(w)-12 b(ork)354 b(concerns)g(what)h(we)g(call) g(minimal)g Fq(R)p Fs(-paths;)379 b(ho)-30 b(we)g(v)-18 b(er)354 b(the)5978 21579 y(primary)309 b(concern)h(is)g(ho)-30 b(w)310 b(to)g(complete)g(the)g(abbre)-30 b(viation)310 b(when)h(it)f(is)f(ambiguous,)j(some-)5978 23084 y(times)302 b(using)h(heuristics.)375 b(DJ)302 b(tak)-12 b(es)303 b(adv)-30 b(antage)304 b(of)e(re\003ection)i(to)f(complete)g(its)g (queries.)7859 24981 y(Mendelzon)478 b(and)f(W)-97 b(ood)478 b([11])f(sho)-30 b(w)476 b(the)i(computational)g(intractability)f(of)g (\002nding)5978 26486 y(actual)277 b(paths)f(in)h(an)f(object)h(graph,) 282 b(e)-30 b(v)-18 b(en)277 b(without)f(the)h(presence)g(of)f (inheritance.)367 b(W)-97 b(e)277 b(a)-24 b(v)g(oid)5978 27992 y(this)467 b(dif)-30 b(\002culty)467 b(because)h(we)g(are)g (searching)f(only)h(for)f(potential)h(paths)f(based)h(on)g(local)5978 29497 y(meta-information,)352 b(and)343 b(we)g(therefore)f(accept)h (the)g(possibility)f(of)g(tra)-24 b(v)-18 b(ersing)341 b(nodes)i(that)5978 31003 y(are)303 b(not)g(actually)g(on)g(a)h(path)f (to)g(the)g(tar)-22 b(get)303 b(class.)7859 32900 y(The)268 b(XP)-18 b(ath)268 b([3])f(language)h(is)g(used)f(to)h(specify)f(sets)g (of)g(elements)h(in)g(XML)f(documents.)5978 34405 y(XP)-18 b(ath)435 b(uses)g(a)g(succinct)h(notation)g(some)-30 b(what)435 b(lik)-12 b(e)436 b(ours;)500 b(for)435 b(e)-18 b(xample,)469 b(the)436 b(XP)-18 b(ath)435 b(e)-18 b(x-)5978 35911 y(pression)392 b Fl(A//B)j Fs(refers)d(to)i(the)f(set)g(of)g(all) h Fl(B)p Fs(-objects)f(reachable)h(from)f(the)h Fl(A)p Fs(-object.)647 b(The)5978 37416 y(semantics)479 b(of)h(an)h(XP)-18 b(ath)480 b(e)-18 b(xpression)479 b(is)h(an)g(unordered)g(set)g(of)g (objects.)907 b(This)479 b(closely)5978 38922 y(matches)350 b(the)g(algorithms)f(as)h(presented)f(in)h(section)g(5,)362 b(although)350 b(our)g(implementation)g(in)5978 40427 y(DJ)342 b(also)g(captures)g(the)h(paths)f(by)h(allo)-30 b(wing)342 b(visitors)f(to)i(be)f(called)h(on)g(all)g(objects)f(in)g (those)5978 41933 y(paths.)5978 45783 y Ft(9)1328 b(Conclusions)331 b(and)g(Futur)-24 b(e)331 b(W)-100 b(ork)5978 47952 y Fs(W)j(e)230 b(ha)-24 b(v)-18 b(e)231 b(presented)f(a)g(semantics)g (for)g(a)g(declarati)-30 b(v)-18 b(e)231 b(speci\002cation)f(of)g (object-graph)g(tra)-24 b(v)-18 b(er)-24 b(-)5978 49458 y(sals.)375 b(Our)302 b(or)-22 b(g)-6 b(anization)304 b(separates)e(the)h(concerns)g(of)7796 52683 y Fh(\017)606 b Fs(The)303 b(search)g(or)f(tra)-24 b(v)-18 b(ersal)302 b(to)h(be)g(performed,)7796 55185 y Fh(\017)606 b Fs(The)303 b(visits)f(to)h(objects)g(of)f(dif)-30 b(ferent)302 b(classes)g(to)h (be)h(e)-18 b(x)g(ecuted)303 b(along)h(the)f(w)-12 b(ay)-79 b(,)303 b(and)7796 57687 y Fh(\017)606 b Fs(The)267 b(details)h(of)f (the)h(or)-22 b(g)-6 b(anization)268 b(of)g(the)g(object)g(graph,)274 b(which)269 b(is)e(reconstructed)g(by)9008 59192 y(re\003ection.)7859 62417 y(Our)441 b(deri)-30 b(v)g(ation)440 b(of)h(an)g(ef)-30 b(fecti)g(v)-18 b(e)440 b(computation)h(for)g(FIRST)f(illustrates)g (that)h(a)g(rela-)5978 63923 y(tional)396 b(formalism)f(is)h(the)g (right)g(approach)g(to)h(e)-18 b(xpress)395 b(the)h(dif)-30 b(ferent)395 b(path)i(concepts)f(that)5978 65428 y(are)303 b(needed;)g(we)h(belie)-30 b(v)-18 b(e)303 b(that)g(this)f(approach)i (will)f(be)g(helpful)g(in)g(other)g(conte)-18 b(xts)303 b(as)g(well.)25297 69672 y(13)p eop %%Page: 14 14 14 13 bop 7859 7638 a Fs(This)291 b(paper)h(w)-12 b(as)291 b(moti)-30 b(v)g(ated)292 b(by)f(the)h(need)g(to)g(ha)-24 b(v)-18 b(e)292 b(a)f(simpler)g(semantics)g(for)g(tra)-24 b(v)-18 b(ersal)5978 9143 y(strate)g(gies)455 b(than)i(the)f(one)h (presented)f(in)h([9].)835 b(No)-30 b(w)457 b(that)g(we)f(ha)-24 b(v)-18 b(e)457 b(a)g(simpler)e(technical)5978 10649 y(core,)371 b(we)358 b(can)g(hope)h(to)e(e)-18 b(xplore)358 b(questions)f(lik)-12 b(e:)485 b(When)359 b(the)f(class)f(graph)h (changes,)371 b(does)5978 12154 y(the)424 b(adapti)-30 b(v)-18 b(e)424 b(program)f(ha)-24 b(v)-18 b(e)424 b(to)g(change?)739 b(F)-18 b(or)424 b(what)g(kind)g(of)g(conte)-18 b(xts)423 b(is)h(an)g(adapti)-30 b(v)-18 b(e)5978 13660 y(\(or)379 b(aspect-oriented\))h(program)f(correct?)608 b(In)380 b(an)g(aspect-oriented)g(program,)399 b(what)381 b(kinds)5978 15165 y(of)341 b(changes)h(in)g(the)g(base)f(program)h(require)f (changes)h(in)g(the)g(aspect)f(code,)352 b(or)342 b(con)-48 b(v)-18 b(ersely)-79 b(,)5978 16671 y(when)422 b(do)h(changes)f(in)g (aspect)g(code)h(require)f(changes)g(in)h(the)f(base)g(code?)734 b(W)-97 b(e)423 b(hope)f(to)5978 18176 y(e)-18 b(xplore)323 b(questions)g(of)g(this)h(kind)f(\002rst)g(in)h(the)g(conte)-18 b(xt)323 b(of)h(DJ)f(and)h(e)-30 b(v)-18 b(entually)324 b(in)f(the)h(more)5978 19682 y(general)303 b(setting)g(of)f(A)-67 b(OP)-135 b(.)5978 23532 y Ft(Refer)-24 b(ences)6584 25702 y Fs([1])605 b(Demeter)303 b(research)g(group,)g(DJ)f(home)i (page,)f(continuously)g(updated.)6584 28203 y([2])605 b Fq(Communications)412 b(of)f(the)g(A)-36 b(CM)p Fs(,)410 b(v)-24 b(olume)412 b(44:10.)f(A)-48 b(CM,)411 b(October)g(2001.)782 b(special)8603 29709 y(issue)302 b(on)h(Aspect-Oriented)g(Programming.) 6584 32211 y([3])605 b(James)290 b(Clark)h(and)f(Ste)-30 b(v)-18 b(e)291 b(DeRose)f(\(eds.\).)409 b(XML)289 b(P)-18 b(ath)291 b(Language)g(\(XP)-18 b(ath\),)292 b(v)-18 b(ersion)8603 33716 y(1.0,)303 b(No)-18 b(v)g(ember)303 b(1999.)6584 36218 y([4])605 b(Erich)417 b(Gamma,)447 b(Richard)418 b(Helm,)447 b(Ralph)419 b(Johnson,)445 b(and)419 b(John)e(Vlissides.)802 b Fq(Design)8603 37723 y(P)-97 b(atterns:)415 b(Elements)323 b(of)h(Reusable)f (Object-Oriented)g(Softwar)-45 b(e)p Fs(.)502 b(Addison-W)-97 b(esle)-18 b(y)-79 b(,)8603 39229 y(1995.)6584 41730 y([5])605 b(Y)-121 b(annis)437 b(E.)f(Ioannidis)h(and)g(Y)-121 b(ezdi)437 b(Lashkari.)865 b(Incomplete)437 b(path)g(e)-18 b(xpressions)436 b(and)8603 43236 y(their)353 b(disambiguation.)598 b(In)353 b Fq(Pr)-55 b(oceedings)354 b(of)f(A)-36 b(CM/SIGMOD)353 b(Annual)g(Confer)-45 b(ence)8603 44741 y(on)303 b(Mana)-12 b(g)g(ement)303 b(of)g(Data)p Fs(,)h(pages)f(138\226149.)g(A)-48 b(CM)303 b(Press,)f(1994.)6584 47243 y([6])605 b(Michael)473 b(Kifer)-48 b(,)515 b(W)-97 b(on)473 b(Kim,)515 b(and)474 b(Y)-121 b(ehoshua)473 b(Sagi)-30 b(v)-79 b(.)980 b(Querying)473 b(object-oriented)8603 48749 y(databases.)900 b(In)448 b(Michael)g(Stonebrak)-12 b(er)-48 b(,)484 b(editor)-48 b(,)484 b Fq(Pr)-55 b(oceedings)448 b(of)g(A)-36 b(CM/SIGMOD)8603 50254 y(Annual)261 b(Confer)-45 b(ence)262 b(on)f(Mana)-12 b(g)g(ement)262 b(of)f(Data)p Fs(,)269 b(pages)262 b(393\226402,)269 b(San)262 b(Die)-18 b(go,)269 b(CA,)8603 51759 y(1992.)303 b(A)-48 b(CM)303 b(Press.)6584 54261 y([7])605 b(Karl)324 b(J.)g(Lieberherr)-67 b(.)505 b(Component)325 b(enhancement:)420 b(An)325 b(adapti)-30 b(v)-18 b(e)324 b(reusability)g(mech-)8603 55767 y(anism)473 b(for)f(groups)h(of)f(collaborating)i(classes.)979 b(In)473 b(J.)g(v)-30 b(an)473 b(Leeuwen,)516 b(editor)-48 b(,)515 b Fq(In-)8603 57272 y(formation)386 b(Pr)-55 b(ocessing)384 b('92,)407 b(12th)385 b(W)-112 b(orld)386 b(Computer)g(Congr)-45 b(ess)p Fs(,)406 b(pages)386 b(179\226185,)8603 58778 y(Madrid,)303 b(Spain,)g(1992.)g(Else)-30 b(vier)-67 b(.)6584 61279 y([8])605 b(Karl)268 b(J.)g(Lieberherr)-67 b(.)360 b Fq(Adaptive)269 b(Object-Oriented)f(Softwar)-45 b(e:)358 b(The)269 b(Demeter)f(Method)8603 62785 y(with)396 b(Pr)-55 b(opa)-12 b(gation)394 b(P)-97 b(atterns)p Fs(.)730 b(PWS)396 b(Publishing)e(Compan)-18 b(y)-79 b(,)419 b(Boston,)g(1996.) 731 b(616)8603 64290 y(pages,)303 b(ISBN)g(0-534-94602-X.)25297 69672 y(14)p eop %%Page: 15 15 15 14 bop 6584 7638 a Fs([9])605 b(Karl)447 b(J.)g(Lieberherr)f(and)h (Boaz)h(P)-18 b(att-Shamir)-67 b(.)897 b(T)-42 b(ra)-24 b(v)-18 b(ersals)445 b(of)i(Object)g(Structures:)8603 9143 y(Speci\002cation)378 b(and)g(Ef)-30 b(\002cient)377 b(Implementation.)676 b(T)-85 b(echnical)378 b(Report)g(NU-CCS-97-)8603 10649 y(15,)267 b(Colle)-18 b(ge)259 b(of)e(Computer)i(Science,)267 b(Northeastern)258 b(Uni)-30 b(v)-18 b(ersity)-79 b(,)266 b(Boston,)h(MA,)258 b(Sep.)8603 12154 y(1997.)5978 14656 y([10])605 b(V)-73 b(ictor)536 b(M.)f(Mark)-12 b(o)-30 b(witz)535 b(and)g(Arie)h(Shoshani.)1180 b(Object)536 b(queries)f(o)-18 b(v)g(er)535 b(relational)8603 16162 y(databases:)474 b(Language,)364 b(implementation,)h(and)353 b(application.)594 b(In)351 b Fq(9th)i(International)8603 17667 y(Confer)-45 b(ence)304 b(on)f(Data)g(Engineering)p Fs(,)g(pages)g(71\22680.)g(IEEE)f(Press,)g(1993.)5978 20169 y([11])605 b(A.)462 b(O.)f(Mendelzon)h(and)g(P)-135 b(.)462 b(T)-90 b(.)461 b(W)-97 b(ood.)944 b(Finding)461 b(re)-18 b(gular)461 b(simple)g(paths)h(in)f(graph)8603 21674 y(databases.)528 b(In)332 b Fq(Pr)-55 b(oceedings)332 b(of)f(the)h(15th)g(Confer)-45 b(ence)333 b(on)f(V)-135 b(ery)332 b(Lar)-45 b(g)-12 b(e)332 b(Databases,)8603 23180 y(Mor)-45 b(gan)303 b(Kaufman)g(pubs.)g(\(Los)f(Altos)g(CA\),)h (Amster)-45 b(dam)p Fs(,)303 b(pages)g(185\226194,)g(1989.)5978 25681 y([12])605 b(Erich)383 b(J.)f(Neuhold)i(and)f(Michael)g (Schre\003.)693 b(Dynamic)384 b(deri)-30 b(v)g(ation)382 b(of)h(personalized)8603 27187 y(vie)-30 b(ws.)436 b(In)303 b Fq(Pr)-55 b(oceedings)302 b(of)i(the)f(14th)g(VLDB)f(Confer)-45 b(ence)p Fs(,)304 b(pages)f(183\226194,)h(1988.)5978 29689 y([13])605 b(Doug)349 b(Orleans)g(and)g(Karl)g(Lieberherr)-67 b(.)583 b(DJ:)348 b(Dynamic)i(Adapti)-30 b(v)-18 b(e)349 b(Programming)f(in)8603 31194 y(Ja)-24 b(v)-30 b(a.)534 b(In)334 b Fq(Re\003ection)g(2001:)437 b(Meta-le)-18 b(vel)334 b(Ar)-45 b(c)-18 b(hitectur)-45 b(es)333 b(and)h(Separ)-18 b(ation)333 b(of)h(Cr)-55 b(oss-)8603 32700 y(cutting)467 b(Concerns)g Fs(,)507 b(pages)467 b(73\22680,)508 b(K)-30 b(yoto,)507 b(Japan,)h(September)467 b(2001.)g(Springer)8603 34205 y(V)-135 b(erlag.)5978 36707 y([14])605 b(Jens)400 b(P)-18 b(alsber)c(g,)424 b(Cun)401 b(Xiao,)426 b(and)400 b(Karl)h(Lieberherr)-67 b(.)748 b(Ef)-30 b(\002cient)399 b(implementation)i(of)8603 38212 y(adapti)-30 b(v)-18 b(e)334 b(softw)-12 b(are.)535 b Fq(A)-36 b(CM)333 b(T)-67 b(r)-18 b(ansactions)333 b(on)h(Pr)-55 b(o)-12 b(gr)-18 b(amming)333 b(Langua)-12 b(g)g(es)334 b(and)g(Sys-)8603 39718 y(tems)p Fs(,)303 b(17\(2\):264\226292,)g(March)f(1995.)5978 42219 y([15])605 b(Jan)439 b(V)-135 b(an)441 b(den)f(Bussche)g(and)f (Gottfried)h(V)-156 b(ossen.)872 b(An)440 b(e)-18 b(xtension)440 b(of)f(path)h(e)-18 b(xpres-)8603 43725 y(sions)537 b(to)g(simplify)g (na)-24 b(vig)-6 b(ation)537 b(in)h(object-oriented)f(queries.)1186 b(In)538 b(Stef)-12 b(ano)537 b(Ceri,)8603 45230 y(Katsumi)384 b(T)-97 b(anaka,)405 b(and)384 b(Shalom)h(Tsur)-48 b(,)403 b(editors,)h Fq(Deductive)385 b(and)f(Object-Oriented)8603 46736 y(Databases)p Fs(,)438 b(pages)411 b(267\226282,)439 b(Phoenix,)g(Arizona,)g(1993.)412 b(Springer)e(V)-135 b(erlag,)440 b(Lec-)8603 48241 y(ture)303 b(Notes)g(in)g(CS,)g(No.)h (760.)25297 69672 y(15)p eop %%Trailer end end