Abductive Matchmaking using Description Logics

1 Motivation

We describe several scenarios in which matchmaking [Di Noia et al., 2003; Sycara et al., 2002; Di Sciascio et ar, 2001; Trastour et al., 2002] is necessary, starting with a human sit­ uation and moving to more automated ones.

Human matchmaking. Imagine you are looking for an apartment in London, UK. On a local newspaper, you p~b­ lished a classified ad, which we call D (for Demand), askmg the following:

Apt. required: Soho, 2 rooms, smoker, dog, garden, max 600/month. Phone xxx-yyyyy

Since no one phoned you, you open a copy of the same news­ paper, and start filtering a long list of classified ads ~ffering apartments to rent. You might encounter the followmg ad, that we call S1 (for Supply):

Apt. centre (Piccadilly), car place, fireplace, 2 rooms. Phone zzz-wwwww

Then you wonder if this offer fits your needs. The match be­ tween Soho and Piccadilly depends on some domain knowl­ edge- actually, they are consistent, although Piccadilly does not imply Soho. Then S1 does not mention that dogs and smokers are allowed, but this does not necessarily mean that they are not (open-world assumption). It does not mention a garden too, but there is a car place, which could be turned into a small garden if it is open air and private. Should you phone to inquire sl first, or phone first the following 3.!:

AAA Apt. in London. Phone sss-ttttt Here it is not just a problem of hypothetical reasoning, it is also a problem of giving some total order to offers that are compatible with yours, presumably trying to maximize the probability of finding a good offer in few phone calls - but wait: if these offers would match, why they didn't phone you?

Software agents matchmaking. A similar scenario, but for the fact that agents may actively look for a matching coun­ teroffer, instead of simply posting their offer. So they may actually call you ...

Matchmaking in Electronic marketplaces. The same sce­ nario, but with some sort of standardized language to describe supplies and demands, and maybe some centralized facilita­ tor for matchmaking, e.g, containing the necessary domam knowledge.

Service Discovery. Either for software agents or in e­ marketplaces, the offers may describe a general service in some standardized language, such as the simple 128-bit string of Bluetooth, or the more structured DAML-S.

The third and fourth scenarios are more amenable to au­ tomated matchmaking, since they imply a standardized lan­ guage and ontology. However, observe that also in the first and second scenarios, when supplies and demands are ex­ pressed in heterogeneous forms, matchmaking is not a mere schema/data integration problem. In fact, integration tech­ niques [Madhavan et ar, 2001] may be employed to make heterogeneous supplies and demands comparable; but once they are reformulated in a comparable way, one is still left with true matchmaking problems: i) given a proposal, are there co{llpatible counteroffers? ii) if there are many com­ patible counteroffers, which are the most promising ones (and why)?

2 Principles for matchmaking

We now discuss in detail various technical options for per­ forming matchmaking, first trying to highlight limitations of non-logical approaches, and then discussing the general Knowledge Representation principles that a logical approach may yield.

First of all, we note that if supplies and demands are simple names or strings, the only possible match would be identity, resulting in an all-or-nothing approach to matchmaking. This is the approach taken by Bluetooth, whose Service Discov­ ery Protocol tries to match Universally Unique Identifiers of services and requests. Although effective for fixed techni­ cal domains, such an approach misses the fact that proposals usually have some sort of structure in them. Such a structure could be exploited in order to evaluate "interesting" inexact matches.

Vector-based techniques taken by classical Information Re­ trieval can be used, too, thus reverting matchmaking to sim­ ilarity between weighted vectors of stemmed terms, as pro­ posed in the COINS matchmaker [Kuokka and Harada, 1996] or in LARKS [Sycara eta/., 2002]. Obviously lack of doc­ ument structure in descriptions would make matching only probabilistic and strange situations may ensue, e.g., the de­ mand "Apt. with two Rooms in Soho pets allowed no smokers" would match the supply "Apt. with two Rooms in Soho, no pets, smokers allowed".

A further possibility is to use sets of words to describe the structure of supplies and demands. We consider these de­ scription as a particular case oflogical description, and move on to Description Logics (DLs). Hence, from now on we suppose that supplies and demands are expressed in a DL £, equipped with a model-theoretic semantics. We suppose also that a common ontology for supplies and demands is estab­ lished, as a TBox Tin£. Now a match between a supply S and a demand D could be evaluated according to T. This framework ensures the first property that we would like to hold for matchmaking, namely, an open-world assumption.

Property 1 (Open-world descriptions) The absence of a characteristic in the description of a proposal should not be interpreted as a constraint of absence. Instead, it should be considered as a characteristic that could be either refined later, or left open if it is irrelevant for the issuer of the pro­ posal.

Moreover, if all constraints of a demand D were fulfilled by a supply S, but not vice versa, then S should be among the top ranked supplies in the list of potential partners of the demander, while D should not appear at the top in the list of potential partners of the supplier.

Property 2 (Non-symmetric evaluation) A matchmaking system may give different evaluations to the match between a supply S and a demand D, depending on whether it is trying to match S with D, or D with S- i.e., depending on who is going to use this evaluation.

There are three relations between concepts expressing sup­ plies and demands, that we consider meaningful in match­ making: implication, consistency, and inconsistency.

In the first case, T f= (D !;;; S), i.e., constraints imposed by D imply those of S, and vice versa if T f= (S !;;; D). This relation extends the previous set-based inclusion to gen­ eral concepts. If both T f= (D !;;; S) and T f= (S !;;; D), then D and S should be considered equivalent in T. This relation extends exact matching, making syntax differences irrelevant. In case of consistency, D n S is satisfiable in T. Then, there is a potential match, in the sense that the con­ straints of neither proposal exclude the other. This relation has been highlighted also by other researchers [Trastour et a/., 2002]. However, that proposal lacks a ranking between different potential matches. In the third case, D n S is unsat­ isfiable in T. Although also in this case a matching could be defined [Di Noia eta/., 2003], we do not treat this case here for lack of space. Hence, from now on we concentrate on po­ tential match only. We now highlight some principles that ­ we believe - every ranking function should have in logical matchmaking.

First of all, if a logic is used to give some meaning to de­ scriptions of supplies and demands, then proposals with the same meaning should have the same ranking, independently of their syntactic descriptions.

Definition 1 (Syntax independence in ranking) A ranking of matches is syntax independent if for every pair of supplies S1 and S2, demand D, and ontology T, when S1 is logically equivalent to S2 then S1 and S2 have the same ranking forD, and the same holds also for every pair of logically equivalent demands D1, D2 with respect to every supply S .

For example, an apartment S1 , described as available for the summer quarter, should have the same rank - with re­ spect to a request - as another S2 , identical but for the fact that it is described to be available for june-july-august. Clearly, when the logic admits a normal form of expressions -as CNF or DNF for propositional logic, or the normal form of concepts for the DL of CLASSIC [Borgida eta/., 1989]­ using such a normal form ensures by itself syntax indepen­ dence.

We now consider the relation between ranking and impli­ cations. We go back to the descriptions with sets of words, since they are easy to read through. Let D be a demand and S1, S2 be two supplies defined as follows :

D {apartment, soho, two Rooms , pets Allowed}

sl {apartment , soho, boiler , quiet}

S2 {apartment, soho, boi ler, quiet, lastFloor}

In this case, the characteristics that S2 adds to S1 are irrele­ vant for D. Hence, whatever the rank for S1, the one for S2 should be the same. If instead we let

S3 = {apartment, soho, boiler, quiet, petsAllowed}

then s3 should be ranked better than s l since it adds a char­ acteristic required by D. We generalize this example to con­ cepts, and state the following definition.

Definition 2 (Monotonicity of ranking over subsumption)

A ranking of potential matches is monotonic over subsump­ tion whenever for every demand D, for every pair of supplies S1 and S2, and ontology T, if S1 and S2 are both potential matches forD, and T F (S2 !;;; Sl), then s2 should be ranked either the same, or better than S1, and the same should hold for every pair of demands D1, D2 with respect to a supply S.

Intuitively, the above definition could be read of as A rank­ ing is monotonic over subsumption if: the more specific, the better. Observe that we use the word "better" instead of using any symbol:::;, 2:. This is because some rankings may assume that "better" means "increasing" (towards either infinity, or 1) while others may assume "decreasing" (towards 0). Observe also that the above definition refers only to potential matches, i.e., consistent matches - otherwise, .l would be the best match (being the most specific concept), which is obviously not the case.

We remark that the properties and definitions we stated in this section are independent of the particular DL employed, or even the particular logic chosen. For instance, the same properties could be stated if propositional logic was used to describe supplies, demands and the ontology. In this respect, we believe that this section keeps its significance also if one chooses more expressive DLs such as SHOQ(D) [Horrocks and Sattler, 2001] or DAML [Paolucci eta!., 2002] .

3 Abduction in Description Logics

We tend to follow the notation of [Eiter and Gottlob, 1995] for propositional abduction whenever possible, and adapt it to our setting.

Definition 3 Let .C be a DL, C, D, be two concepts in .C. and T be a set of axioms in .C. A Concept Abduction Problem (CAP), denoted as (.C, C, D, T ), is finding a concept HE .C such that T f!= C n H = _i, and T f= C n H ~ D.

We use P as a symbol for a CAP, and we denote with SOL(P) the set of all solutions to a CAP P. Observe that if C n D is unsatisfiable in T, then trivially SOL(P)= 0, i.e. , there are no solution to P if C and D are not a poten­ tial match. Hence from now on we concentrate on the case T f!= C n D = _l.

As propositional abduction extends implication, a CAP ex­ tends concept subsumption. But differently from proposi­ tional abduction, we do not make any distinction between manifestations and hypotheses, which is usual when ab­ duction is used for diagnosis. However, diagnosis is not our domain of application for abduction, and when mak­ ing hypotheses about properties of goods in e-marketplaces, there is no point in making such a distinction. This unifor­ mity implies that if C n D is satisfiable in T, then D E SOL( (.C, C, D, T) ), i.e., there is always the trivial solution D to a non-trivial CAP (.C, C, D, T). Interpreted in our e­ marketplace application domain, it means that if I hypoth­ esize for the counteroffer exactly all my specifications, the counteroffer trivially meets my specifications. Since one wants to model Occam's razor, some minimality in the hy­ potheses must be defined. In the following definition, we denote with ~T the subsumption relation between concepts w.r.t. a TBox T.

Definition 4 Let P=(.C, C, D, T) be a CAP The set SOLc(P) is the subsetofSOL(P) whose concepts are max­ imal under ~T· The set SOL< (P) is the subset of SOL(P) whose concepts have minimum length.

We note that being maximal under ~T is still a minimality criterion, since it means that no unnecessary hypothesis is as­ sumed. It can be proved that the two measures are incompa­ rable.

Proposition 1 There exists a CAP P such that the two sets SOLr;;_(P) and SOLsJP) are incomparable.

Proof. It is sufficient to consider D = A1 n A2 n A3, C = A1 , and T = {B ~ A2 n A3}. The logic is even propositional. Then A2 n A3 E SOLr;;_( (.C, C, D, T) ), B E SOL< ( (.C, C, D, T) ), and neither solution is in the other set. 0- The proof highlights that, although ::;-minimality could be preferable for conciseness, it is heavily dependent on T. For every concept H E SOL(P), it is sufficient to add the axiom A = H to get a ::;-minimal solution A.

A third minimality criterion is possible for DLs that admit a normal form as a conjunction of concepts, that is, every concept C in .C can be rewritten as an equivalent concept C1 n · · · n Cn. This is the case for .C = A.CN, and for the DL of the CLASSIC KR system. We call such a normal form CNF, in analogy with propositional logic.

Definition 5 Let P=(.C, C, D, T) be a CAP in which .Cad­ mits a CNF The set SOLn(P) is the subset of SOL(P) whose concepts are minimal conjunctions, i.e., if C E SOLn(P) then no sub-conjunction ofC is in SOL(P) . We call such concepts irreducible solutions ofP.

It turns out that n-minimality subsumes both ~y-minimality and ::;-minimality. This is not a surprise, since n-minimality is a form of ~0-minimality, i.e., maximality for subsumption w.r.t. an empty TBox.

Proposition 2 For every CAP P in which .C admits a CNF, both SOLr;;_(P) and SOL~ (P) are included in SOLn(P) .

Proof. If a concept C is not n-minimal, then it is not ::;-minimal, and the same for ~T. o

3.1 Computational Complexity

Since Concept Abduction extends Concept Subsumption w.r.t. a TBox, complexity lower bounds of the latter problem carry over to decision problems related to a CAP.

Proposition 3 Let P=(.C, C, D, T) be a CAP. If Concept Subsumption w.r.t. a TBox in .C is a problem C-hard for a complexity class C, then deciding whether a concept belongs to SOL(P) is both C-hard and co-C-hard.

Proof. Hardness for C comes from the fact that C is subsumed by DinT iffT E SOL(P) . o

Hence, if .C contains the DL A.C, then deciding whether a concept belongs to SOL(P) is EXPTIME-hard [Donini, 2003] for a general TBox T, but it is PSPACE-hard ifT con­ tains only acyclic concept axioms [Calvanese, 1996].

Regarding upper bounds, a simple result can be derived from the fact that D is always a solution of the CAP (.C, C, D, T) - although not always a minimal one. First of all, a total length-lexicographic order -< can be defined over concepts as follows: given two concepts C, D E .C, let C -< D if either ICI < IDI, or both ICI = IDI and C is lexicographically before D. Based on this total order, an algorithm for finding a ::;-minimal solution of a CAP, using polynomial space relatively to an oracle for subsumption in .C, is the following:

input: a CAP P= (.C, C, D, T), with T f!= C n D = _l

output: a concept in SOL< (P)

variables: concept x E .C -

begin

x:=T;

while lxl < IDI do if (T f= C n x [;;; D and T ~ C n x [;;; .l) then return x ; x := next concept following x in -< endwhile; return D end.

The above algorithm uses polynomial space (considering the two calls to subsumption as an oracle) since it just tries all concepts with less symbols than D, and returns D if it does not find a shorter solution. Therefore, it provides an upper bound on the complexity of CAP, depending on the complex­ ity class to which subsumption in .C belongs to. Although this result does not directly lead to a practical algorithm, it puts an upper bound on the complexity of the problem, hence on the complexity of every optimal algorithm.

Theorem 1 Let P=(.C, C, D, T) be a CAP. Ifsubsumption in .C belongs to a complexity class C that is included in PSPACE, then finding a concept in SOL< (P) is a problem in PSPACE. Otherwise if PSPACE is included inC, then finding a concept in SOL5. (P) is a problem in C.

Given that the problem of finding a solution cannot be simpler than the corresponding decision problem, we can conclude with some general results about :=;-minimal abduction.

Theorem 2 Let P=(.C, C, D, T) be a CAP, with .C a DL whose expressiveness is between A.C and the DL containing concept constructors n, U, · , 3R.C, V R.C and role construc­ tors U, role chain, transitive-reflexive roles, role identity, role inverse. Then finding a concept in SOL< (P) is a problem EXPTIME-complete when Tis a general TBox.

Proof. Hardness results for A.C are in [Donini, 2003]. Mem­ bership result for the most expressive logic comes from converse-Propositional Dynamic Logic [Vardi and Wolper, 1986]. D

Hence, for a general TBox the best known algorithms re­ quire exponential time and also exponential space (unless one proves PSPACE = EXPTIME).

When the TBox is acyclic, complexity results for subsump­ tion imply that finding a concept in SOL5.(P) is a problem PSPACE-complete for DLs whose expressiveness is between A.C£ [Calvanese, 1996] and A.CC [Baader and Hollunder, 1991]. Even for the simplest logic A.C, the problem is co­ NP-hard [Calvanese, 1996].

3.2 Irreducible solutions in A£N

In this section, we assume that T of a CAP P= (.C, C, D, T) is always acyclic. Finding an irreducible solution is easier than finding a :=;-minimal or a [;;;-minimal solution, since a greedy approach can be used to minimize the set of conjuncts in the solution: starting from C n D, delete one redundant conjunct at a time from D. However, instead of starting from C n D, we adapt a structural subsumption algorithm [Borgida and Patel-Schneider, 1994] that collects all concepts that should be conjoined to C to be subsumed by D . The al­ gorithm operates on concepts in normal form; roughly speak­ ing, this form is obtained by expanding concept names with their definition in T, and then applying the following rewrit­ ing rules as much as possible:

VR.CnVR.D --+ VR.CnD Cn.l --+ .l (~ n R) n (::::; m R) --+ .l if n > m VR . .l --+ VR . .l n (::::; 0 R)

In the following algorithm, we denote the fact that a con­ cept A appears as a conjunct of a concept C with A E C.

Algorithm findlrred(P); input: a CAP P= (.C, C, D , T), with .C=A.CN, acyclic T, and T ~ C n D = .l output: concept HE SOLn(P) (where H = T means that Cis already subsumed by D) variables: concept H begin H:=T; for every concept name y in D ify is not inC then H := H n y; for every concept k n R) in D such that there is no concept (~ m R) in C with m ~ n H := H n (~ n R); for every concept(::::; n R) in D such that there is no concept(::::; m R) inC with m ::::; n H := H n (::::; n R); for every concept V R.E in D if there exists V R.F in C then H := H n findlrred( (.C, F, E, T) ); else H := H n findlrred( (.C, T , E, T) ); /*now HE SOL(P), but it might be reducible*/ for every concept Hi in H if H without HiE SOL(P) then delete Hi from H; return H;

end.

It can be proved that the concept H returned by f indlrred() is indeed an irreducible solution of P. As for complexity, the expansion of the TBox in the construction of the normal form can lead to an exponential blow-up, as demonstrated by Nebel in [1990]. And anyway, a polynomial algorithm cannot be expected since subsumption in A.C with an acyclic T is co-NP-hard [Calvanese, 1996]. However, in the cited paper Nebel argues that the expansion is exponential in the depth of the hierarchy T; if the depth ofT is O(log ITI), then the expansion is polynomial, and so is the above algorithm.

Theorem 3 Let P= (.C, C, D , T) be a CAP, with .C=A.C. and T an acyclic TBox whose depth is always bounded by O(log ITI). Then finding an irreducible solution to P is a problem solvable in polynomial time.

In order to rank the proposals in a marketplace according to how "near" they are to a given proposal D, we take the number of concept names in the irreducible solution returned by the above algorithm. Although this makes the rank depend on the algorithm, it can be easily proved that this definition is in accordance with the principles highlighted in Section 2. Moreover, the fact that a concept H is actually computed makes it easy to devise an explanation facility, in case a user wants to know why a given proposal has been ranked before another. This transparency is crucial for our electronic busi­ ness scenario, where we must give the user reasons to trust the system. In the next section, we show the results of an exper­ iment comparing the rank obtained by our deployed system and the rank provided by some users in the same scenario.

4 Experiments

Using the highlighted properties as a formal specification we designed and implemented a prototype facilitator. The system embeds an adapted NeoClassic reasoner, the C++ implemen­ tation of the original Classic. The rationale of the choice of the Classic system, apart from the obviously useful availabil­ ity of concrete datatypes and the possibility to extend its func­ tionalities through test functions, is its polynomial time infer­ ence. The system receives a description of demand/supply. Then, the reasoner checks the description for consistency; if it fails, based on the reasoner output, the system provides an er­ ror message stating the error occurred. Otherwise the proper matchmaking process takes place, and the system returns a ranked set of matches. When no exact match is available, The user may investigate potential matches. In this process he/she is helped by the system ranking. We believe that de­ gree of conformance of an automated matchmaking facilitator to users' perception is of extreme importance, especially in a setting as our own, which ranks and categorizes matches. To evaluate the ability of the system to meet users' expectations we set up a little experimental framework.

We selected all apartments-rental advertisements from the dedicated section of a local newspaper on Oct. 6th of last year. We subdivided them in two sets, demands (23 adver­ tisements) and supplies (39 advertisements). It is notewor­ thy that, at least for the single-day pick we made, we were not able to detect any exact match. We submitted to twenty volunteers of various sex and age, a questionnaire that in­ cluded 8 items. Each item was one demand and a set of up to eight supplies, or one supply and a set of up to eight demands. Volunteers were asked to rank, according to their judgement, elements of each set with respect to the given ad­ vertisement, with the following question: Order the follow­ ing Demands(Supply) with respect to the given Supply (De­ mands) as you would contact them had you issued the given Supply (Demand). Volunteers were given unlimited time and in average it took approximately half hour to complete the questionnaire. Then the same sets of items were submitted to the reasoner. As a general consideration, the response of the reasoner was quite close to the users' ones, and consid­ ering average volunteers orderings the system ranking was in agreement with the human judgement almost always. Aver­ age percentage of deviation from the mean values determined by the users on the whole experiment was 8.3.

As an example, we show here in more detail results of the evaluation for a single demand/supplies matching process, extracted form the experimental setting. Let us consider the example demand: student looking for a nice 112 bed flat, ch, furnished, kitchen, washing machine. Price: 150

Also consider the following advertisements submitted as demand (and Bedroom (all toLetFor Student) (at-least 1 hasBed) (at-most 2 hasBed) (at-least 1 hasFacilities) (all hasFacilities (and WashingMachine NoAutonomousHeating FullyFurnished)) (all hasServices Kitchen) (all price (maximum 150))}

supplyl (and Bedroom (all price (minimum 120)) (all pricelncludes (and Bill TVPrice)) (all hasFacilities (and FullyFurnished Spatious)))

supply2 (and (all price (minimum 150)) (at-least 2 hasRoom) (at-most 2 hasRoom) (all hasRoom Room) (at-least 2 toLetFor) {at-most 2 toLetFor) {all toLetFor {and Couple Student)) (at - least 1 depositRequired) (all depositRequired Yes))

supply3 (and (at-least 1 depositRequired) (all depositRequired Yes) (all price (minimum 80)) Bedroom (all toLetFor (and Student NoSmoker Worker (all sex Female))))

supply4 (and SingleRoom {all toLetFor (and NoSmoker Student)) (at-least 2 occupants) (all price (minimum 120)))

supplyS (and OoubleRoom (all toLetFor Single) (all hasFacilities (and Lounge Garden)) (all hasServices Kitchen) (all price (minimum 85)) (all priceincludes Council Tax))

supply6 (and Bedroom (at-least 1 occupants) (all price (minimum 81)) (all toLetFor Female) (all hasFacilities (and WashingMachine TV VCR)))

supply? (and Bedroom (all price (minimum 95)) (all occupants Family) (at-least 2 occupants) (all toLetFor (and Student Professional (all sex Female))))

supplyB (and Flat (at-least 2 hasBed) (at-most 2 hasBed) (all toLetFor Student) (all hasFacilities ADSL) (all price {minimum 95))))

Figure 1: Neoclassic descriptions of demand and supplies

supplies:

• Supply 1: large, fully furnished room, price includes cable TV and bills. Price: 120
• Supply2: double room, suit a couple or two girls, required deposit. Price: 150
• Supply]: room to rent, suit a non smoking female student with worker, international preferred, deposit required. Price: 80
• Supply4: single room in clean flat for nosmoker quiet student, sharing with 2 others. Price: 120
• Supply5: db/ room in shared house, suit single person, use of lounge, kitchen , garden, rent includes council tax. Price: 85
• Supply6: female to share a room in a residential area flats hare, washing machine, TV, VCR. Price: 81
• Supply7: large room in family houses hare with 2 adults, suit prof I student female, viewing recommended. Price: 95
• Supply8: 2 bed flat, perfect for student, dble bed ADSL com­ puter beneath. Price: 600

The translation of these advertisements into Classic, in ac­ cordance with our ontology is pictured in Figure 1. Table 1 shows results provided from the matchmaking algorithm comparing the system provided ranking and the average vol­ unteers orderings for demands w.r.t. to a supply. Figure 2 shows the same results in a graphical form. Notice that, while volunteers gave strictly ranked orderings, the system could also provide equal ranking for various matches. Poly­ gons represent a range for the system total order of supplies, when there are equally ranked supplies. For example, Sup­ ply 3 and 7 are given the same rank by the system, so they could be equally put in fourth or fifth position when supplies are given a total order. Hence we consider correct system ranks for Supply 3 and 4, because users' rank fall inside the polygons, while we consider incorrect system placement of Supply 2 and 7 (dotted lines mark the difference).

5 Conclusion

Motivated by the matchmaking problem in electronic mar­ ketplaces, we have studied abduction in DLs. We have pre­ sented suitable definitions of the problem, and have shown how they can model commonsense reasoning usually em­ ployed in analyzing typical commercial advertisements. Al­ though we used the simple DL A.CN, our definitions and logical framework can be used also when a more expressive DL is used. Of course in this case more complex algorithms should be devised. To substantiate these ideas we have im­ plemented a prototype based on the devised specifications adapting a NeoClassic reasoner, and presented experiments that show the correspondence between the system behavior with human users judgement.

Acknowledgements

We thank Peter Patel-Schneider for valuable suggestions on CLASSIC, Simona Colucci and Marco Mottola for use­ ful implementations. This work has been supported by MURST project CLUSTER22, by EU-POP project "Negotia­ tion Agents for the Electronic Marketplace", by PON project ' 'Tecnologie innovative per Ia valorizzazione e Ia fruizione dei Beni Culturali ", by CNR projects LAICO, and "Metodi di Ragionamento Automatico nella modellazione ed analisi di dominio ".