Journal of Universal Computer Science, vol. 1, no. 12 (1995), 762-789
`submitted: 11/12/95, accepted: 27/12/95, appeared: 28/12/95ª Springer Pub. Co.
`
`Constraint Agents for the Information Age
`
`Jean-Marc Andreoli, Uwe M. Borgho and Remo Pareschi
`Rank Xerox Research Centre, Grenoble Laboratory
`, chemin de Maupertuis. F-  Meylan, France.
`Email: fandreoli,borgho,pareschig@xerox.fr
`
`Johann H. Schlichter
`Institut fur Informatik, Technische Universitat Munchen
`D- Munchen, Germany.
`Email: schlicht@informatik.tu-muenchen.de
`
`Abstract: We propose constraints as the appropriate computational constructs for
`the design of agents with the task of selecting, merging and managing electronic infor-
`mation coming from such services as Internet access, digital libraries, E-mail, or on-line
`information repositories. Specically, we introduce the framework of Constraint-Based
`Knowledge Brokers, which are concurrent agents that use so-called signed feature con-
`straints to represent partially specied information and can exibly cooperate in the
`management of distributed knowledge. We illustrate our approach by several examples,
`and we dene application scenarios based on related technology such as Telescript and
`workow management systems.
`Key Words: multiagent coordination, agent-interaction, distributed problem solving,
`signed feature constraints, negotiation, cooperation strategies.
`Category: H. . ., I..
`
` Introduction
`
`New electronic sources of information, such as E-mail, Internet access and on-
`line information repositories ood the desktop environment of users with an
`evergrowing ow of information which, in order to be exploitable, demand ef-
`cient management. The inundation of electronic data coming from all kind of
`sources must convert into real knowledge in order to benet the whole range of
`users from business people to casual surfers and shoppers on the Internet. Intel-
`ligent agents CACM, ; Wooldridge and Jennings,  interacting through
`multiagent systems have been proposed as the appropriate answer to this de-
`mand. Indeed, software processes of this kind may one day manage distributed
`knowledge by living on the network" and manipulating electronic information
`on users’ behalf.
`A central question faces us in order to reach an eective deployment of such
`technology: How intelligent agents can be best designed and customized to meet
`users’ individual information needs. The issue at stake concerns essentially one
`of adequate computational support. However, the motivations dier from those
`underlying linguistic frameworks for multiagent systems such as Actors Agha,
`  and Agent-oriented Programming AOP Shoham,  as well as of mul-
`tiagent architectures, either reactive" see e.g. Brooks,  or deliberative"
`Bratman et al.,  or hybrid" Kaelbling and Rosenschein, . In these
`cases the agents are assumed to be situated in an environment which they can
`modify while pursuing their own goals. These goals range from collecting empty
`
`762
`
`

`

`cans, for simple robotic agents, or optimally solving scientic programming prob-
`lems, for software agents in massively parallel multiprocessing architectures, to
`more complex types of activities for correspondingly more complex types of
`agents. Furthermore, the agents communicate either by passing messages as in
`Actor languages or by issuing, declining, or committing to requests, as well as
`performing other speech acts as in the higher-level AOP languages. Thus, these
`agents explicitly communicate with their fellows and implicitly assume their sit-
`uatedness in given environments. By contrast, agents primarily concerned with
`the elaboration and manipulation of information must have a more direct and
`explicit relationship with the environment since by its exploration they derive
`their very raison d’etre. Communication with fellow agents will at times be im-
`plicit and other times explicit: these agents eectively elaborate information and
`then communicate it, either to other agents or to humans. The recipients of infor-
`mation may be unknown to the senders  communication resembles more a radio
`broadcast or a conference presentation than a conversation between entities that
`know each other.
`A computational model should satisfy a few precise requirements in order to
`support this notion of agency:
`
` . By denition these agents continually watch for information that meets pre-
`established criteria. For instance, in a given company, they can routinely
`scan news wires for breaking reports about the company’s current customers,
`whoever they happen to be. Thus, it must be possible to express and imple-
`ment agents’ behavior in terms of a set of criteria through which information
`is ltered and selected. These criteria act as a partial specication of the in-
`formation to come.
`. Electronic information domains are wide open lands where most of the times
`we do not know exactly what we are looking for, nor what we are going to
`nd. In these conditions, a good way to guide our search is to explicitly
`exclude things we are not interested in. This can be conveniently expressed
`by freely mixing positive" and negative" requirements in the specication
`of the behavior of agents. Thus, users should be allowed to feed agents with
`such requests and criteria as nd me all books written by Umberto Eco
`which are not novels" or I am not interested in reports on sales reps from
`Canada Customer Operations".
` . The scope of exploration of agents should be dynamically readjustable to
`optimize their work. As a minimal requirement, they should be capable of
`focusing on targets," thus incrementally reducing their scope as they pro-
`ceed. More intelligence could plausibly come from long-term memory, that is
`the remembrance of things past: They should be able to reuse the knowledge
`they have gained from executing a certain request in the context of other
`requests. Take for instance a request such as nd me all books by Umberto
`Eco which are not novels" and a subsequent request such as nd me all
`books by Umberto Eco which are literary essays."
`. We would also like to implement cooperative behavior of multiple agents
`on given tasks. Cooperation should arise naturally from handling queries
`involving the selection and composition of information from dierent knowl-
`edge repositories often called backends reachable through the Internet.
`Another example is the creation of compound documents on the y from
`preexisting documents, according to some hierarchical description language
`
`763
`
`

`

`like SGML ISO, , with each part of the nal document being assigned
`to a specic agent.
`. Finally, it should be possible to tune interagent communication in terms
`of dierent communication protocols according to such parameters as the
`nature of the problem to be solved, the underlying system architecture, etc.
`
`In this paper we investigate these issues from the point of view of a computational
`construct that has already found widespread application in articial intelligence
`and computer science, namely the notion of constraint. Constraints have been ex-
`ploited mainly in the context of search and combinatorial optimization but their
`signicance is more general and extends to the management and manipulation
`of information. In fact, constraints can be used to provide partial specications
`on the possible values of variables. This paper illustrates how this capability can
`be exploited to implement predened criteria for ltering and selecting informa-
`tion. The specic constraint framework we shall adopt is the Constraint-Based
`Knowledge Brokers CBKBs Andreoli et al., ; Andreoli et al., to appear
`model, which exploits constraints to support knowledge-intensive tasks executed
`by concurrent agents and views the management and manipulation of informa-
`tion in distributed environments as a form of distributed problem solving. A
`CBKB is capable of understanding and enacting both requests" and nega-
`tions of requests," is self-sucient in managing its own scope of exploration over
`a given information domain and is capable of knowledge reuse. Furthermore, dif-
`ferent communication protocols for CBKBs have been dened that can be used
`to tune interagent communication and cooperation.
`The remainder of this paper is organized as follows. In Sect. , we charac-
`terize the notion of multiagent interaction in the context of distributed problem
`solving. Agents are classied and given a set of general requirements. Agent
`cooperation is then illustrated in terms of CBKBs. Two dierent protocols for
`interagent communication are introduced and described, one supporting direct,
`explicit communication and the other supporting group-oriented communication.
`Sect. introduces a specic type of constraints suitable for representing elec-
`tronic information, namely signed feature constraints SFC. In Sect. , SFCs
`are used to illustrate a number of specic issues of information management,
`such as interdependencies, thresholds, and reuse of information. Sect.  explains
`related scenarios. In particular we discuss negotiation in the contract-net proto-
`col, Telescript as a promising agent infrastructure, and workow management as
`an interesting application domain for remote programming. In Sect. , related
`work is discussed. Sect.  concludes the paper.
`
` Multiagent Interaction
`
`The area of Distributed Problem Solving DPS has led to various approaches
`which allow distributed semi-autonomous agents to cooperate in order to solve
`complex problems and accomplish tasks which might not be solvable by one
`individual system. From the problem solving point of view, distribution implies
`the decomposition of the problem into a set of subproblems and the dissemination
`of the subproblems to the appropriate agents which solve them autonomously
`and concurrently. The nal solution of the global problem can be generated
`by composing the solutions of the subproblems. Thus, agents can be viewed as
`problem solvers which cooperate to generate the solution of the global problem.
`
`764
`
`

`

`. Classication
`
`We distinguish between passive and active agents. Passive agents act under
`direct user control. The user explicitly triggers the execution of agent func-
`tions, e.g. sorting and ling electronic messages in the user’s mailbox. Unlike
`passive agents, active agents react to incoming messages, such as requests for
`information or the execution of functions, autonomously or semi-autonomously.
`Autonomous agents may perform actions without user involvement. They have
`enough knowledge about the problem domain and the contextual constraints
`to interpret received messages and react appropriately. During execution, the
`user has no direct control over the agent’s behavior. On the other hand, semi-
`autonomous agents perform routine tasks for the user. Exceptional requests or
`situations are referred to the user who handles them personally. The behavior
`of semi-autonomous agents is directly controlled by the user who has read and
`write access to the rules which specify the agent’s behavior.
`Agents are used in a wide area of dierent application domains ranging
`from robotics, distributed sensoring to Computer-Supported Cooperative Work
`CSCW and information gathering Wayner, . The emerging eld of CSCW
`provides a demanding area for distributed problem solving. CSCW systems need
`to support the interaction of humans and overcome the diculties of tempo-
`ral and spatial distribution. For instance, agents may be used to support the
`scheduling of meetings see Sen and Durfee, . Another related application
`domain is that of workow management and document processing where agents
`might be used to coordinate the tasks and information exchange between tasks
`and humans. The rapid growth of the Internet and the World-Wide Web have
`demonstrated the need for innovative and ecient ways of information gath-
`ering, and this provides the main focus for this paper. The World-Wide Web
`makes available an incredible amount of information; however, in many cases
`the user is unable to nd and extract the desired information eectively. In this
`case agents may be used to collect relevant information, lter the search results
`according to contextual constraints, and present the resulting information to the
`user in an appropriate form. Telescript White, b is an example of system
`providing infrastructural support for this type of agent application.
`The contract-net protocol Smith,  was one of the rst approaches to
`provide a general framework for DPS. It supports an application protocol for
`communication between problem solving agents and facilitates distributed con-
`trol during the problem solving eort. Special emphasis is put on
`
` localizing those agents which are eligible for solving the created subproblems;
` the negotiation between agents for the information exchange with respect
`to subproblem descriptions, required agent capabilities and subproblem so-
`lutions Davis and Smith,  .
`
`The Rank Xerox Research Centre at Grenoble has developed the model of
`Constraint-Based Knowledge Brokers CBKBs which uses constraints to pro-
`vide computational support for DPS. CBKBs explicitly separate aspects of local
`problem solving, based on computations specic to a single agent, from aspects of
`global problem solving, deriving from the interaction of dierent agents. CBKBs
`model active agents which act autonomously and concurrently. In the following
`sections some of the specic capabilities of the CBKB model will be discussed
`in more detail.
`
`765
`
`

`

`In order to eectively cooperate and participate in the problem solving eort,
`an agent must satisfy the following requirements:
`
` an agent must be able to communicate with other agents of the system e.g.
`send and receive requestanswer messages;
` an agent must be able to act upon receipt of messages.
`
`. Cooperation between Agents
`
`The phenomenon of cooperation which is well-known in the human environment
`may also be applied to agent interaction. A number of dierent cooperation
`strategies between agents have been proposed, ranging from strongly hierarchi-
`cal master-slave relationship, to the less hierarchical contract-net Smith, ,
`to the sharing of common goals. In the latter case agents not only exchange
`information with respect to their individual tasks and problems, but they also
`communicate their goals. Thus, the agents follow shared goals when pursuing
`the problem solving activities.
`In general, cooperation between agents is based on explicit communication,
`i.e. agents send messages to transfer knowledge and requests. The message con-
`tent can range from values, formal and informal descriptions, to constraints. The
`CBKB model uses values and constraints to represent knowledge and requests
`for problem solving. The basic message types in the context of DPS are requests
`and answers. Usually messages are completely structured and are only intended
`for agent consumption; the messages are not in human-readable form. The mes-
`sage structures can be tailored to reduce network bandwidth and interpretation
`complexity by the agents. Both the contract-net protocol and the CBKB model
`apply structured messages to model agent interaction. An example for a sys-
`tem which uses semi-structured messages is Object Lens Malone and Lai, ,
`which provides intelligent ltering and dissemination of electronic mail messages.
`Semi-structured messages are based on the notion of a semi-formal system Mal-
`one,   which:
`
` represents and interprets information that is formally specied,
` permits the human user to create and interpret formal information infor-
`mally,
` allows the formal interpretation by the computer and the informal interpre-
`tation by the user to be easily changed.
`
`Semi-formal systems are especially useful in heterogeneous environments
`where there is no clear separation between human tasks and agent tasks. They
`support the co-existence of humans and agents in the same environment. For ex-
`ample, some people use personal agents to cooperate in the distributed meeting
`scheduling process, while other people perform the required requests manually.
`Thus, semi-formal systems facilitate a smooth transition from a purely human-
`oriented environment to a completely agent-based environment. However, semi-
`formal systems use rather complex messages. This creates a signicant network
`load and requires complex interpretation functionality by the agents.
`
`766
`
`

`

`. CBKB Interaction Protocols
`
`Within the CBKB model, two dierent agent interaction protocols have been
`designed:
`
` the request-subrequest protocol;
` the local caching protocol.
`
`. . The Request-Subrequest Protocol
`
`CBKB’s request-subrequest protocol exploits dependencies between agents: the
`request carries an index that is added to all output information sent out as
`answers to the original request. In this way, requester and requestee are directly
`linked. Information is provided only if requested, and is sent only to the agents
`that have explicitly requested it.
`The initial request carries an index which acts as an address for the requesting
`agents, as well as a description of the problem to be solved. A problem descrip-
`tion in a request is instantiated as a constraint on the problem domain. Thus, a
`request is basically a constraint with some additional information such as the
`index. An agent takes the problem description and simplies it into subprob-
`lems. These descriptions of the subproblems are then submitted as subrequests
`in the same way as the initial request. The subrequests are individually indexed
`so that they can be collected into a solution by the requestee agents.
`
`. . The Local-Caching Protocol
`
`The local caching protocol does not link requesters with requestees. By contrast,
`as soon as a solution for a particular subproblem is available, it is broadcast to all
`existing agents. The initial request carries only a description of the problem to
`be solved; no index is associated with it. As before, an agent takes the problem
`description and simplies it into subproblems. However, as a consequence of
`this protocol, for some of the subproblems solutions may already be known to
`the agents. The description of yet unsolved subproblems are then submitted as
`subrequests in the same way as the initial request, i.e. again without index. In this
`way, we obtain a situation of local caching of information for all existing agents,
`thus decreasing the overall amount of trac, as we avoid the re-generation of
`the same requests from dierent requesters. On the other hand, we may end up
`storing information which never gets used.
`
`. . Hybrid Schemes
`
`Obviously, the two protocols above are at the very opposite ends of a spectrum
`of possible protocols and intermediate cases are possible, for instance, when au-
`tomatic deliveries are done for subsets of agents. For many practical applications
`these cases seem to be the most useful, so we need techniques for assigning agents
`to appropriate interest groups," and for allowing exible tuning of group-based
`communication. Furthermore, there are cases where the best strategy for dis-
`tributed problem solving may involve splitting the problem into subproblems
`which are optimally solved according to dierent protocols. Again, we need ex-
`ible ways for expressing such protocols, and for mixing them freely in the overall
`
`767
`
`

`

`solution of a particular problem. Besides, we need ways of guessing the right
`protocol, or the right melange of protocols, for specic problems. This calls for
`contributions from such diverse elds as programming linguistics, learning and
`simulation.
`
` Broker Agents and Constraints
`
`In the CBKB model we formalize the problem-subproblem relationship which is
`at the basis of DPS via the notion of generator. Intuitively, a generator denes the
`decomposition of a given problem into subproblems and the composition of the
`subproblem solutions into the nal solution of the problem. Operationally, gen-
`erators are associated with a special kind of agents, the so-called broker agents.
`A broker incorporates the generator functionality together with the capability
`of dynamically spawning other agents clones of the broker for solving subprob-
`lems. The generator function g is implemented by applying input arguments to it
`and producing corresponding output information which represents the answers
`of the request to the broker.
`
` . Generator
`
`Given an abstract domain of values D, representing pieces of knowledge, a gen-
`erator is a mapping g : Dn ! D, which produces new pieces of knowledge
`from existing ones. The argument ai, i  f ; : : : ; ng of the generator g represents
`a solution of the i-th subproblem. ai may be either a value which was computed
`or retrieved from a database by the agent responsible for the subproblem, or a
`constraint. The number of arguments n of the generator g species the number
`of subproblems created by the broker out of the initial request; the broker has
`the arity n and is called brokern. The arity n is only of local importance; it
`solely depends on the number of subproblems of the decomposed initial request.
`The sender of the initial request has no knowledge of the number of subprob-
`lems created by the brokern. With respect to the decomposition of requests and
`composition of subanswers brokers act as autonomous agents. Thus, it is possible
`that a brokern sends a subrequest to a brokerm where n m. This approach
`to the hierarchical decomposition of requests and recomposition of answers ex-
`ploits insights from deductive frameworks for parsing Pereira and Warren,  
`and database querying Vielle, .
`In the current prototype implementation of the CBKB model the generator g
`needs solutions for all argument positions to apply its function, i.e. the appropri-
`ate agents must have provided solutions for the assigned subproblems. However,
`an extension of the current prototype is envisioned that incorporates more com-
`plex generators which also handle partial solutions, i.e. the solution of the global
`problem is generated from a subset of subproblem solutions. A simple example
`is the creation of a document which consists of several document parts. The
`generator g collects individual document parts and combines them into the nal
`document. If document parts are not available g inserts automatically missing
`subsection" into the nal document.
`As already mentioned earlier the generator g of a broker B composes answers
`to its request r out of the subanswers to subrequests. For an individual subre-
`quest several contacted agents may provide multiple subanswers which return
`
`768
`
`

`

`independently at broker B. Even multiple answers from a single agent may be
`received by the broker B at dierent times. At the receipt of a subanswer the
`generator g attempts to compose an answer to request r out of the newly re-
`ceived subanswer and the already previously received ones. The resulting answer
`will be checked by the broker B against the initial constraint of r in order to
`decide if it represents a valid answer. If there are multiple subanswers for certain
`subrequests available the generator g will construct all possible combinations
`to compose answers for the request r. Suppose the broker B decomposed the
`initial request r into two subrequests r and r. For r the broker B received
`two subanswers, and for r three subanswers. The generator g will construct a
`solution space consisting of six potential solutions for r. By checking the initial
`constraints of r, only valid solutions are extracted from the solution space and
`propagated to the requester of r. In Prasad et al., , a related negotiation-
`driven multiagent retrieval approach is proposed where inconsistencies between
`dierent subanswers are dynamically resolved.
`A set of generators identies a class of subsets of the domain which are stable
`under these generators, that is, if the arguments ai are within the subset, the
`knowledge generated by g is also within the same subset Andreoli et al., .
`The class of stable sets is closed under intersection, so that it has a smallest
`element in the sense of inclusion, given by the intersection of all the stable
`sets. This minimal stable set, also called minimal model, represents the intended
`semantics of the set of generators.
`
` . Knowledge Representation
`
`Brokers are agents which can process knowledge search requests. Knowledge is
`taken here to be any piece of electronic information intended to be publicly
`accessible. Dierent, possibly distributed, information sources are assumed to
`be available, from a simple le in a user’s directory to a database local to a site,
`up to a wide area information service WAIS on the internet, for example.
`When receiving a request, a broker may have sucient knowledge to pro-
`cess it, or may need to retrieve more knowledge. For that purpose, it releases
`subrequests, aimed at other brokers. Thus, knowledge retrieval is achieved by
`the collaboration of all the brokers which are alternatively service providers pro-
`cessing requests and clients of these services generating subrequests. We are not
`concerned here by the infrastructure required to support such collaboration, nor
`by the way knowledge is stored locally within each broker, but rather by the
`knowledge manipulations occurring within each broker.
`In order to collaborate, the brokers must at least understand each other.
`This means that all the requests must be formulated in a common language
`and also all the answers to the requests, even if the brokers may perform
`local translations. Logic provides the adequate language for such a purpose. A
`request can be expressed by a pair hx; P i where x is a logical variable and P
`a logical formula involving x, meaning Retrieve knowledge objects x such that
`the property expressed by formula P holds". Interestingly, an answer to such
`a request can be expressed in the same formalism, i.e. a pair hx; Qi, meaning
`There exists a knowledge object x satisfying the property expressed by formula
`Q". The requirement here is that P must be a logical consequence of Q, so that
`the answer contains at least as much knowledge as the request. Moreover, the
`same logical formalism can be used to capture the scope of a broker, i.e. the
`
`769
`
`

`

`area of knowledge it is concerned with: a broker with scope hx; Ri means I am
`not capable of retrieving knowledge objects x which do not satisfy the property
`expressed by formula R". In many situations, the scope of a broker may vary,
`because it gets specialized or, on the contrary, expands its capacities, either
`externally or due to the knowledge retrieval process itself.
`In other words, logic provides a common language where both requests, an-
`swers and scopes can be expressed. Brokers then perform logical operations on
`these three components. The most important logical operation, from which all
`the others can be reconstructed, is satisability checking, i.e. deciding whether
`some object could satisfy the property expressed by a formula, or, on the con-
`trary, whether it is intrinsically contradictory. Unfortunately, it is well known
`that this operation, for full Classical Logic, is not algorithmic, i.e. it is provably
`impossible to write a program which implements it and always terminates. Given
`this limitation, a lot of research in knowledge representation has been focused on
`identifying fragments of Classical Logic in which satisability is algorithmically
`decidable. The trade-o here is between expressive power and tractability: the
`empty fragment, for example, is obviously tractable, but it is not very expressive!
`A very popular fragment which emerged from this research is known as feature
`constraints". The satisability problem in this case is also known as feature
`constraint solving".
`Traditionally, feature constraints are built from atomic constraints which
`are either sorts or features. A sort is a unary relation, expressing a property
`of a single entity. For example, P:person expresses that an entity P is of sort
`person. A feature is a binary relation expressing a property linking two entities.
`For example, P:employer- E expresses that entity P has an employer, which
`is an entity E. Apart from sorts and features, most feature systems also allow
`built-in relations such as equality and disequality.
`
` . Constraints
`
`The full fragment of feature constraints, where the atomic components men-
`tioned above are allowed to be combined by all the logical connectives con-
`junction, disjunction, negation and quantiers, although very expressive, is
`hardly tractable. Therefore, we consider a subfragment, called basic feature
`constraints" BFC, where negation and disjunction are simply forbidden. Ef-
`cient constraint solving algorithms have been proposed for this subfragment.
`However, completely disallowing negation puts strong limitations on the kind of
`operations a knowledge broker may wish to perform.
`In particular, we have identied a very common and powerful operation
`named scope-splitting", which relies on the use of negation. Indeed, a broker
`may wish to split its scope, specied by a pair hx; P i according to a criterion ex-
`pressed by a formula F , thus creating two brokers with scope P ^ F and P ^ :F .
`Thus, a broker in charge of bibliographic information may wish to split its scope
`into two new scopes: books written after ", which can be represented by
`the BFC
`
`X
`
`X : book,
`X : year - Y, Y 
`
`770
`
`

`

`and its complement, i.e. books written before  or documents which are
`not books"; this latter scope cannot be expressed using BFC, because negation
`and disjunction cannot be dispensed with. We have found that the scope split-
`ting operation is needed in many situations, for example to implement brokers
`capable of memorizing and reusing information gathered during their lifetime.
`Our approach presents on the one hand a fragment of feature constraints, called
`signed feature constraints" SFC, which allows limited use of negation, pre-
`cisely capable of expressing the kind of scope splitting mentioned above, and on
`the other hand, an ecient constraint solving method for SFC.
`
` . . Signed Feature Constraints
`
`A signed feature constraint is composed of a positive part and a list of negative
`parts, both of them being basic feature constraints. For example, the following
`signed feature constraint
`
`P +
`
`P : person,
`P : employer- E, E : "Xerox"
`- P : nationality- N, N : "American"
`- P : spouse- P’,
`P’: person,
`P’: employer- E’, E’: "Xerox"
`
`species a Xerox employee who is not American and is not married to another
`Xerox employee. We can represent this SFC graphically as in Fig. . The round
`boxes denote the entities logical variables, the sort relations unary are rep-
`resented by dashed arrows labeled by the name of the sort in a square box, the
`feature relations binary are represented by plain arrows labeled by the name of
`the feature in a square box. The built-in predicates not present in the example
`are represented by rhombuses. The positive part of the SFC is contained in the
`top box and marks the distinguished entity of the scope P in the example by
`a double round box. The negative parts of the SFC are contained in the lower
`boxes in grey.
`The main interest of SFC comes from the following property:
`
`If the scope of a broker is represented by an SFC eo, and this scope is
`split by a BFC e, then the two resulting split scopes e+; e(cid:0) are both
`SFC.
`
`Indeed, e+ is obtained by merging the positive part of eo with the BFC e; and
`e(cid:0) is obtained by extending eo with a new negative part containing e alone.
`For example, assume a broker in charge of a bibliographical database contain-
`ing various documents books, videos etc. about Art, but not authored by an
`American. It is represented by the SFC
`
`X +
`
`X : topic- T, T : "Art"
`- X : author- A,
`A : nationality- N, N : "American"
`
`771
`
`

`

`person
`
`employer
`
`E
`
`P
`
`"Xerox"
`
`nationality
`
`N
`
`"American"
`
`E’
`
`"Xerox"
`
`spouse
`
`employer
`
`P’
`
`person
`
`Figure : A signed feature constraint the negative parts are in grey.
`
`It may be split by the constraint books written after ", expressed by the
`BFC
`
`X
`
`X : book,
`X : year- Y, Y 
`
`The resulting scopes are simply
`
`X +
`
`X : book,
`X : topic- T, T : "Art",
`X : year- Y, Y 
`- X : author- A,
`A : nationality- N, N : "American"
`
`i.e. Art books written after  but not by an American author" and
`
`772
`
`

`

`X +
`
`X : topic- T, T : "Art"
`- X : author- A,
`A : nationality- N, N : "American"
`- X : book,
`X : year- Y, Y 
`
`i.e. Art documents not authored by an American but not books subsequent to
` ".
`
` . . Solvin