SOFTWARE AND HARDWARE IN PATTERN RECOGNITION AND IMAGE ANALYSIS SYSTEMS Logic Object-Oriented Model of Asynchronous Concurrent Computations1 A. A. Morozov Institute of Radio Engineering and Electronics, Russian Academy of Sciences,ul. Mokhovaya 11, Moscow, 125009 RussiaAbstract—In this paper, we consider the model of concurrent computations developed for logic programming of Internet agents. The purpose of creating this model of computations is to ensure the mathematical strictness of searching and recognizing information on the Internet. In the developed model of computations, the inter- acting concurrent processes have classical model-theoretic semantics. The model of computations is based on the new principle of interaction of processes, which do not require delay for synchronization. On the basis of this model, we have developed and implemented the concurrent object-oriented logic language and also the tools for visual logic programming of Internet agents.
also the notions of soundness and completeness of logicprograms.
Internet agents are programs that automate retrieval,
recognition, extraction, and analysis of information on
Over the past decade, a large number of methods
the Internet oriented toward the needs of an individual
and means of logic programming of Internet agents
user (or group of users). Agents differ from the widely
were developed. They are based on different modifica-
used Internet retrieval systems in the following:
tions and extensions of the Prolog language and also on
(1) they can autonomously operate during long peri-
nonclassical logics (linear, modal, F-Logic, etc.) [1, 3,
ods of time (days, weeks, or more) for performing the
4, 24]). However, up to now, no mathematical apparatus
which could provide sound and complete work of logic
(2) as any other program, once created, an agent can
programs (agents) in a dynamic external environment
be used many times, whereas a query to a universal
(i.e., in conditions of permanent change and augmenta-
retrieval system invokes a single operation of informa-
tion of information in the Internet) was created.
To solve this problem, we have developed the logic
At present, no universally accepted definition of
agents exists. However, programs that are autonomous,
model of concurrent computations based on the princi-
reactive (i.e., react to external stimuli), proactive (e.g.,
ple of repeated proving of subgoals [21–26]. In the
capable of planning further actions themselves), and
framework of our model, the Internet agent is a system
exhibit a social behavior (if there is a system of several
of interacting concurrent processes. The main distinc-
agents) [1, 2] are conventionally called agents.
tion of the developed model is the fact that it presumesthe existence of classical model-theoretic semantics of
One of the most interesting and perspective
approaches to programming Internet agents is logic
Internet agents functioning under conditions of infor-
programming of agents [1, 3, 4]. The urgency of this
mation change and augmentation. For this purpose, in
approach is determined, in particular, by the fact that
the framework of the model, the classical model-theo-
the ideology and principles of logic programming cor-
retic semantics of individual concurrent processes and
respond to the problems of retrieval, recognition, and
of the system of interacting processes as a whole are
analysis of ill-structured and also hypertext informa-
tion [24, 26]. However, the main advantage of logicprogramming is the fact that, in the framework of this
In the first section of the paper, we consider the prin-
approach, there exist criteria for evaluating the mathe-
cipal elements of our computational model: processes,
matical strictness of information processing methods,
messages, and the so-called “residents.” In the second
namely, the model-theoretic semantics of programs and
section, we consider the declarative semantics andmathematical properties of concurrent programs. In the
1 This work was supported by the Russian Foundation for Basic
third section, we discuss the use of the developed
Research, project nos. 00-01-00560 and 03-01-00256.
model for the visual component-oriented programmingof Internet agents. In the fourth section, our approach toprogramming Internet agents is compared with other
Pattern Recognition and Image Analysis, Vol. 13, No. 4, 2003, pp. 640–649. Original Text Copyright 2003 by Pattern Recognition and Image Analysis. English Translation Copyright 2003 by MAIK “Nauka /Interperiodica” (Russia).
LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS
The principle of interaction of concurrent processes
developed by the author and his colleagues is a gener-alization of the method of speculative computationsapplied to the field of artificial intelligence and also to
Fig. 1. States of the process. (a) Proven process, (b) failed
the hardware implementation of computing devices.
The idea of speculative computations implies that cer-tain branches of the algorithm can be implemented inadvance, prior to the moment when it becomes clear
(3) We have developed a special mechanism to
whether the obtained data are needed for further pro-
transfer information between processes (the so-called
gram execution. The use of this idea and the mathemat-
residents) resembling the setof statement of the stan-
ical apparatus of logic programming makes it possible
not to delay concurrent processes for their synchroniza-
Thus, the processes can interact through common
tion. Instead of delaying the processes, we use a modi-
variables and also by means of predicate calls. That is
fication of logic inference; as a result, the general
why, in contrast to the classical object-oriented compu-
scheme of interaction of concurrent processes can be
tational model using only one kind of message, two
kinds of messages are distinguished in our model,
Each process performs computations with data
available at the present moment. If some data are not
When a process handles the obtained message, its
yet received, the process performs computations with
state changes. The period of process execution corre-
incomplete data. As is shown below, the developed
sponding to the processing of a certain message is
strategy of execution of logic programs is sound with
called a phase of process execution. At each phase of
respect to their declarative semantics; therefore, any
the process execution, the corresponding subgoals of
results obtained during computations are correct with
the proof (logic actors [21–26]) are proved in accor-
respect to the declarative semantics of the program.
dance with the information that has come from the out-
Computations with incomplete input data can be
side. Depending on the results of repeated proving of
regarded as a certain form of computing by default.
actors, the process is transferred into one of the follow-
Subsequently, when new or modified input data arrive
in the process, the conducted computations are modi-
(1) A proven process. This state is characterized by
fied and the earlier obtained results are refined.
the consistency of all actors of the process (the proof of
Modification of logic inference in our computation
model is based on the principle of the repeated proving
(2) A failed process. This state is characterized by
of subgoals [21–26]. The developed model is imple-
the fact that actors of the process are inconsistent.
mented in the concurrent version of the object-oriented
(3) An unused process. The unused process can be
Actor Prolog logic language [21, 26]. Therefore, to
considered as some offline component of a computing
simplify the presentation in this paper, we will use the
device. The processes automatically pass into the
notions and syntactic notation of this language.
unused state and automatically recover from this statewhen certain special flow messages are obtained. These
The process in the concurrent Actor Prolog is the
The process in the unused state performs no opera-
class instance, whose clauses are executed concurrently
tions, and all messages sent to it are accumulated in the
relative to clauses of other processes. In the Actor Pro-
buffer. Using the unused processes, the agent changes
log, the processes are denoted by enclosing the con-
its structure in the course of execution.
structor of the class instance in double parentheses:
The difference between flow and direct messages
The transmission of information between processes
in our model is carried out by means of the following
(1) Direct messages are passed directly from one
process to another (in the form of the predicate call),
(1) A process can perform an asynchronous predi-
while the flow messages are passed from one to many
processes (by changing the values of common vari-ables).
(2) A process can pass information to other pro-
cesses by changing the value of their common variable.
2 In the definition of the Actor Prolog [21], one more auxiliary state
The arguments of the corresponding constructors of
arising in the course of process construction is considered addi-
class instances can be such common variables.
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
Fig. 2. Flow messages. Fig. 3. Ports of processes.
(2) Direct messages are not lost in the course of
empty value is received through the suspending port,
communication, while the flow messages can cancel
the process is automatically passed to the unused state.
one another if a new (updated) value of a common vari-
When the values of all suspending ports of a process
able arrives before the processing of the previous value
become not equal to # and to empty values, it will auto-
Before the direct and flow messages are transmitted,
Using the suspending ports, one can create recursive
all unbound variables in the composition of the corre-
definitions of processes, i.e., definitions of classes
sponding predicate and terms are replaced by a special
which recursively include the constructors of instances
constant #. This prevents the chaining of variables that
of the same class. In the general case, an attempt to cre-
belong to different processes. This transformation does
ate the instance of such a class leads to the construction
not violate the soundness of the logic program in
of an infinitely large number of processes and to mem-
respect to its declarative semantics.
ory overflow. However, the use of suspending ports
Flow messages are processed in the Actor Prolog in
makes it possible to gradually construct new processes
the following way. When the value of the common vari-
as information arrives at the suspending ports of the
able V that links the recipient process P to other pro-
corresponding constructors. Thus, the Actor Prolog
cesses is changed, the destructive assignment V :=
makes it possible to describe systems consisting of infi-
NewValue is performed in the process P. The result of
nite number of processes and create new processes as
this operation is the repetitive proving of certain actors
of the process P. In Fig. 2, we present the graphic sym-bols used to denote flow messages.
The ports which are neither protecting nor suspend-
Common variables that connect processes are called
ing are called plain (simple). In Fig. 3, we present
ports. In our computational model, special means for
graphic notation for different ports of processes.
controlling flow message transmission are introduced.
In our computing model, direct messages are asyn-
The process can declare a certain value of the common
chronous, as also are the flow messages. In the course
variable protected. In this case, other processes are for-
of execution of clauses of a process, it can call the pred-
bidden to assign this variable the ordinary (unpro-
icate of another process (i.e., send a direct message) by
tected) values. A protected value of a common variable
using special operations of sending direct messages:
can only be replaced by another protected value. In the Actor Prolog, the special keyword protecting is intro-
Target << predicate (A, B, …, C),
duced for creating protected values of common vari-ables. The keyword is assigned to the definitions of
Target <– predicate (A, B, …, C).
slots of class instances and also to the arguments of theconstructors of processes, i.e.,
Such an operation is always successful and does not
affect the further execution of the sending process. The
((ClassName,…, protecting: attributeN=ValueN,…)).
sending of direct messages is suspended up to the com-
Note that, in the case where the process passes to the
pletion of the current phase of process execution and is
state failed or unused, the flow messages transmitted by
performed if and only if this phase is completed suc-
it (including protected ones) are canceled. To do this,
cessfully. In addition, the operations of sending direct
special empty values are sent through all the ports of
messages are canceled in the backtracking of the logic
the process; these values can be further replaced by any
protected or unprotected values by other processes.
The infix << denotes the co-called informational
Another keyword, suspending, is used to declare
direct messages, and the infix <– denotes the switching
the so-called suspending (switching off) ports:
direct messages. These kinds of direct messages differ
((ClassName,…, suspending: attributeN=ValueN,…)).
Suspending ports serve for automatic passing of
(1) As a result of processing of a switching direct
processes in the unused state and for their automatic
message, the process can become either proven or
recovering from this state. When a special constant # or
failed, while after processing of an informational direct
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS
Fig. 4. Direct messages. Fig. 5. Resident.
message, the process is always proven. If the execution
of the function to its owner in the form of a protected
of an informational direct message fails, this message is
simply ignored and the process restores its former state.
The resident permanently observes the state of the
(2) In contrast to switching direct messages, pro-
assigned target process. After each change in the state
cessing of informational direct messages is suspended
of the target process, the resident repeats the construc-
until the recipient process becomes proven. The sus-
tion and sending of the list of values of the function. In
pended messages are accumulated in the buffer.
addition, the resident can receive the information from
In Fig. 4, we present the graphic notation used for
its owner in the form of flow messages through the
arguments of the corresponding atomic formula. When
Note that the rules of processing flow messages cor-
new values of arguments are received, the resident also
respond to the rules of processing switching direct mes-
performs the repetitive execution of the assigned func-
sages considered above. Thus, the flow messages can
tion and sends the collected information.
Figure 5 gives a graphic representation of the resi-
In our computing model, the resident is a certain
active entity observing the state of the assigned (target)
1.4. An Example of the Graphic Description
process and sending the collected information to its
owner. The owner of a resident is a certain process. Inthe Actor Prolog, the residents are defined via special
Let us consider an example of the graphic descrip-
tion of the Internet agent collecting data with the use ofthe Google and Rambler search engines. In Fig. 6, the
slot = target_world ?? function (A, B, …, C).
functional diagram is presented. It uses the notation
Such a formula can be assigned in the form of the
argument of the constructor of the class instance or as a
Process 1 performs the interaction with a user. It
definition of a slot as a part of the class. In the general
inputs the list of keywords and sends to Processes 2 and
case, the following correspond to each resident of the
3 the switching direct message, which starts up the
search process. Processes 2 and 3 interact with the cor-
(1) The owner of the resident. The owner of the res-
responding search engines and accumulate the received
ident is the process that has created it.
addresses in local databases. The collected addresses
(2) The atomic formula function(A, B, …, C). This
are included into lists by residents and passed to Pro-
formula denotes the call of a certain function (nondeter-
cess 4 in the form of flow messages. Process 4 merges
ministic in the general case) which must be executed in
the lists of addresses and passes them to Process 5,
the target process. The functions in the Actor Prolog are
which performs additional filtering of the received ref-
implemented with the help of the standard technique of
erences. The necessary technique of checking Web
pages is implemented in Process 6. Note that Process 6
(3) The target process of a resident, target_world.
passes itself into Process 5 via the flow message inorder that Process 5 uses it as a filtering instrument. The
(4) A certain common variable slot. Using this vari-
list of checked addresses is passed to Process 7, which
able, the resident sends the collected information to its
demonstrates the found addresses in the dialog box and
makes it possible for the user to look through the found
A resident automatically executes the assigned
resources with the use of a standard Internet browser.
function in the search space of the target process. Theresident creates the list of all computed values of the
In the next section, we consider the declarative
function and then orders this list and deletes repeated
semantics of the elements of the computing model out-
elements. After that, the resident sends the list of values
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
Fig. 6. Graphic description of the Internet agent.
cesses of a program that has reached a successful final
Model-theoretic semantics will be defined in the fol-
The model-theoretic semantics of logic programs is
lowing way. Below, we will define the scheme of trans-
an important instrument evaluating the mathematical
formations of an arbitrary concurrent logic program P
strictness of implemented algorithms. Using the model-
into a sequential program P', for which the existence of
theoretic semantics, one can evaluate the following:
the classical model-theoretic semantics is guaranteed.
(1) Soundness of algorithms. As will be shown
The declarative semantics of the program P' will be
below, the Actor Prolog ensures the soundness of pro-
taken as the semantics of the source program P.
grams (including concurrent ones) with respect to their
To construct the desired program P', we perform the
model-theoretic semantics. Thus, we can be sure that
the program will never compute (incorrect) values that
(1) We remove from the text of the program P all
do not belong to its model-theoretic semantics.
(2) Completeness of algorithms. Provided that cer-
(2) We replace all the constructors of processes in
tain conditions are fulfilled, we can guarantee the com-
the text of the program by usual constructors of class
pleteness of the logic program. This means that the pro-
instances (that is, in the constructors of processes, we
gram implements an exhaustive search and finds all
replace double parentheses by ordinary ones). Thereby
existing solutions of the posed problem. Unfortunately,
the concurrent logic program will be transformed into a
far from all logic programs are complete in respect to
(3) We model the operation of suspending ports via
An important merit of our computing model is the
auxiliary predicates. For example, the behavior of the
fact that it ensures the existence of classical (that is,
process with the goal statement goal and two suspend-
based on the first-order predicate logic) model-theo-
ing ports x and y will be modeled by means of redefin-
retic semantics of concurrent programs.
ing the goal statement. The new goal statement goal'will be defined in the following way:3
Definition 2.1. We say that the logic program has
attained its successful final state if (i) all the processes
of the program are proven or unused, (ii) activation ofresidents is not required, and (iii) the processing of no
messages by processes and residents is required. Definition 2.2. The result computed by the program
3 In the Actor Prolog, the operator == corresponds to the ordinary
is the values of common variables connecting the pro-
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS
point of view of the declarative semantics, these mes-
not x == #,
(6) We remove from the text of the program the key-
words protecting.
(7) We have obtained a sequential object-oriented
not y == #,
program. The object-oriented constructions of the
Oldgoalstatement.
Actor Prolog can be easily modeled in the pure Prolog
The auxiliary predicate ground_term is nondeter-
by simple renaming the predicates and adding certain
ministic; it bounds the argument with all elements of
auxiliary arguments. The detailed algorithm of such
the Herbran universe. This predicate is necessary in
transformations can be found in [22].
order to guarantee the correctness of using the state-
As a result of transformations, we obtain the
ment not at the given point of computations. In the gen-
sequential program P' in the pure Prolog with the not
eral case, this predicate outputs an infinite number of
statement. The not statement is not used in the Actor
answers; therefore, this transformation can lead to infi-
Prolog language. Thus, in the program P', the not state-
nite loop in the case where the standard control strategy
ment is used only for modeling the special construc-
of Prolog is used. However, at the moment, the only
tions of the language considered above. Therefore, P' is
thing that matters is the presence of the declarative
stratifiable and, hence, possesses the classical model-
(4) The operation of residents will be also modeled
Definition 2.3. The model-theoretic semantics of
by redefining goal statements and auxiliary predicates.
the concurrent program P is the model-theoretic
For instance, if the initializer of one of the slots is a con-
semantics of the sequential program P' constructed
structor of the resident of the form slot = target??func-tion(a, b, …, c), we redefine the goal statement goal of
Theorem 2.1. A concurrent logic program is sound
in respect to its model-theoretic semantics. Sketch of a proof. Considering the AND-tree of the
program P in the course of transformations (1)–(7), one
can verify that it can only decrease (at Step 1). Thus, the
AND-tree of the program P' covers by no means lesssolutions than the program P. That is, the program P
The operation of constructing the list of solutions
cannot compute the solutions not covered by the pro-
returned by the function function(A, B, …, C) will be
gram P' (and, therefore, incorrect with respect to the
implemented according to the following scheme:
Of course, in the general case, the concurrent pro-
gram P does not possess the completeness relative to its
model-theoretic semantics. To ensure the complete-
not is_element(Result, Results),
ness, it is necessary to impose constraints on the syntaxof the program.
setof(A, B,…, C,[Result | Results], Total);
Theorem 2.2. The concurrent program P is com-
plete in respect to its model-theoretic semantics if we
not has_another_solution(A, B,…, C, R),
(1) There are no nonlogic built-in predicates in the
has_another_solution(A, B,…, C, Results) :-
(2) Direct messages are not used. Information
between processes is transmitted only via the flow mes-sages. not is_element (Result, Results).
(3) The program does not get caught in an endless
The auxiliary predicate is_element checks whether
loop in the course of executing goal statements and
the value Result is contained in the list. The auxiliary
predicate sort puts the elements of the list in order andremoves the repeated elements. For sorting the ele-
(4) The functions called by residents always return
ments of the list, we use the lexicographic ordering.
The auxiliary predicate ground_term guarantees the
(5) Predicates computing data which are then sent
correctness of the use of the not statement.
by means of flow messages are deterministic.
(5) We remove all operations of sending direct mes-
(6) Information is transmitted between processes
sages from the text of the program. As was already
along one-direction channels only. The unidirectional
noted, direct messages in our model are strictly asyn-
data transmission in the Actor Prolog can be modeled
chronous and are always successful. Thus, from the
by means of the keyword protecting.
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
(7) There is a partial ordering of processes exchang-
achieve a real economic effect from using agents, it is
ing information. That is, there is no recursive transmis-
necessary to create technologies for programming
sion of data between the processes and residents in the
agents which would maximally facilitate and simplify
the development of such programs by final unskilled
(8) All values computed by processes and residents
users. Ideally, the creation of the Internet agent must be
which must be passed to other processes and residents
as simple as the compilation of the query to the general-
are ground (i.e., they do not contain unbound vari-
purpose retrieval system. The developed methods and
means of logic programming create necessary prerequi-sites for the solution of this problem. Based on the cre-
Sketch of the proof. There are five possible reasons
ated mathematical apparatus, the Actor Prolog, concur-
for incompleteness of the concurrent program in
rent object-oriented logic language, is developed (the
respect to the declarative semantics. The first reason is
definition of the language including all new features
incompleteness of computations performed inside
can be found on the site listed in [21]). In the recent ver-
some process. To eliminate this reason, conditions (1)
sions of the language, special means for supporting the
and (3) are introduced. The second possible reason is
development of the Internet agents were introduced:
the impossibility to transfer the backtracking betweenprocesses. Conditions (5) and (6) guarantee that if a
(1) predefined classes for getting information
process has computed and passed a certain solution into
according to HTTP and FTP Internet protocols;
another process, then no other solution exists. There-
(2) visual programming means including the trans-
fore, the backtracking is not necessary since it all the
lator of SADT diagrams into the concurrent Actor Pro-
same would not help to find other solutions. The third
log and the user interface management system based on
possible reason for incompleteness is the replacement
of unbound variables by the constant # during informa-
(3) packages and other syntactic means necessary
tion transmission between processes. Condition (8)
for the implementation of the visual component-ori-
removes this reason. The fourth reason is infinite com-
putations which may arise in the course of programexecution. Such infinite loops of a program are pre-
At present, we have implemented the operating pro-
vented by conditions (3), (4), and (7). The fifth possible
totype of the system of logic programming of Internet
reason is the presence of several successful final states
intelligent agents on the basis of the developed mathe-
of a program. Specifically, the program can have sev-
matical apparatus and the Actor Prolog language. The
eral final states if (a) the direct messages with a gener-
developed system makes it possible to create agents for
ally unpredictable order of the processing are used in it;
the retrieval and analysis of information on the Internet.
and (b) data are transmitted recursively and it is impos-
The use of the object-oriented logic approach substan-
sible to predict the order in which the processes related
tially simplifies the creation of Internet agents and also
by common variables will be executed. To prevent these
their subsequent support and modification.
cases, we have introduced conditions (2) and (7),respectively. Therefore, provided that the enumeratedconditions (1)–(8) are met, the program will be com-
plete in respect to the model-theoretic semantics.
The developed method of programming the Internet
Thus, the concurrent computations in our model
agents and the model of concurrent computations
possess not only the operational but also the model-the-
embodies several ideas, each of which must be consid-
oretic semantics. The soundness of the program is guar-
ered separately and compared with earlier approaches.
anteed, and, under certain conditions, the completenessof the program with respect to the model-theoreticsemantics is also guaranteed. This means, in particular,
4.1. Visual Programming of Internet Agents
that the logic language can be used for writing concur-
rent programs that perform an exhaustive search. This
The idea of visual programming of Internet agents
makes it possible to conclude that the developed model
via functional diagrams was successfully realized ear-
of concurrent computations and the concurrent object-
lier by Mosconi and Porta [6]. They developed the
oriented logic language implement the principles of
VIPERS system [6] on the basis of a special kind of data
logic programming mathematically strictly.
flow diagrams. As compared with our system of visualprogramming of Internet agents, the VIPERS systempossesses better graphic interface, but the blocks of dia-
grams are implemented in the imperative language.
Thus, the VIPERS system does not support the declara-
In the majority of cases, the tasks of collecting and
tive semantics of Internet agents and does not ensure
processing information which require automation with
the mathematical strictness of procedures of search and
the help of intelligent agents have individual character
recognition of information in the dynamic Internet
and are formulated by concrete users. Therefore, to
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS
4.2. Concurrent Programming of Agents
putations is used in the OZ language [14] instead ofbacktracking.
The expedience of using the flow parallelism for the
development of languages for programming Internet
Our model can also be considered as the implemen-
agents was also demonstrated in the WebL project of
tation of the idea of speculative computations, since the
Kistler and Marais [7] (on the basis of combinators
synchronization of concurrent processes is not used in
developed by Cardelli and Davies [8]), Webstream by
the Actor Prolog. This means that, in our model of com-
Hong and Clark [9], WebScript by Zhang and Keshav
puting, concurrent processes never wait for data from
[10], and information gathering plans by Barish and
other processes and all computations performed by the
Knoblock [11]. The listed languages are imperative
program are in fact speculative computations. Thus, our
and, thus, have the same drawback as the system
model of computing is a mathematical basis for imple-
menting speculative computations in multiagent sys-tems.
The logic programming languages for the Internet
agents developed earlier, such as the concurrent Log-icWeb developed by Davison and Loke [5], W-ACE by
Pontelli and Gupta [12], Jinni by P. Tarau [13], OZ [14]developed under the direction of G. Smolka, DLP
The mathematical apparatus of logic programming
developed by Eliens and de Vink [15], ObjVProlog-D
of intelligent agents performing the search and recogni-
by Malenfant, Lapalme, and Vaucher [16], etc. [4],
tion of information in a complex structured dynamic
ensure the existence of the declarative semantics of
Internet environment is developed. The developed
agents but do not support the modification of logic
mathematical apparatus is based on the principle of the
inference in the dynamic external environment and,
repetitive proving of subgoals, which makes it possible
therefore, do not ensure the mathematical strictness of
to modify the logic reasoning during and after the exe-
cution of logic programs by putting them in correspon-dence with the new information incoming from outside.
Based on the developed apparatus of modifiable rea-
4.3. Modifiable Reasoning in Multiagent Systems
soning, we have created the Actor Prolog, concurrent
As a promising approach to the logic programming
object-oriented logic language, which ensures the cor-
of Internet agents in the dynamic external environment,
rectness of logic programs (intelligent agents) function-
the use of nonclassical (and, in particular, nonmono-
ing under conditions of permanent change and updating
tonic logic systems) [3, 17, 18] is considered. We have
chosen a principally different way, strictly adhering to
The developed tools make it possible to create per-
the formalism of classical first-order logic. In our
sonal systems (agents) for gathering and analyzing
model of computations, the modification of reasoning
information on the Internet. The use of the object-ori-
necessary for the correct logic interpretation of changes
ented logic approach substantially simplifies the cre-
in the external world is implemented via a special con-
ation of Internet agents, as well as their subsequent sup-
trol strategy of logic language based on the principle of
port and modification. The developed approach sup-
repeated proofs. This made it possible to mathemati-
ports visual and component-oriented programming of
cally strictly interpret the dynamic character of the
Internet environment without loosing the expressiveand deductive properties of the classical first-orderpredicate logic. Note that our approach is free from the
drawbacks of nonmonotonic logic systems, such as
The author is grateful to Doctor of Physics and
absense of general validity of deduced formulas (in the
Mathematics Yu. V. Obukhov for help and support in
classical sense), dependence of the result on the order
implementing the project, to Academician Yu.I. Zhuravlev
of application of the inference rules, and the high prob-
and Professor V. A. Zakharov for fruitful discussions of
ability of looping of logic programs.
the problem of describing the declarative semantics ofmultiagent systems, and also to Candidate of Physicsand Mathematics S. V. Remizov, who provided soft-
4.4. Speculative Computations in Multiagent Systems
ware for debugging the prototype of the Actor Prolog.
One of the most interesting directions in the pro-
gramming of agents is speculative computations. Usingthis principle for the control of the process of gathering
data from the Internet, Barish and Knoblock [11]
1. Sadri, F. and Toni, F., Computational Logic and Multi-
achieved a significant increase in Internet agent speed. agent Systems: A Roadmap, 1999; available at
The same idea at a higher level of abstraction was stud-
http://citeseer.nj.nec.com/sadri99computational.html.
ied in the work of Inoue, Kawaguchi, and Haneda [19]
2. Huang, Z., Eliens, A., van Ballegooij, A., and
and also in the work of Satoh and Yamamoto [20]. It
de Bra, P., A Taxonomy of Web Agents, IEEE Proc.
should be also noted that the idea of speculative com-
First Int. Workshop on Web Agent Systems and
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
Applications (WASA 2000), 2000; available at
15. Eliens, A. and de Vink, E.P., Asynchronous Rendez-
http://wasp.cs.vu.nl/wasp/papers/wasa2000.ps.
Vouz in Distributed Logic Programming, in de Bak-ker, J.W, de Roever, W.P., and Rozenberg, G.,
3. Eiter, T., Fink, M., Sabbatini, G., Tompits, H., Using
Methods of Declarative Logic Programming for Intelli-
Springer, 1993, pp. 174–203; available at http://
gent Information Agents, Theory and Practice of LogicProgramming, 2002, vol. 2, no. 6, pp. 645–709; avail-able at http://arxiv.org/abs/cs.MA/0108008.
16. Malenfant, J., Lapalme, G., and Vaucher, J.,
4. Davison, A., Logic Programming Languages for the
ObjVProlog-D: Distributed Object-Oriented Pro-
Internet, in Kakas, A. and Sadri, F., Eds., Invited Submis-
gramming in Logic, Object Oriented Systems, 1996,
sions for Computational Logic: From Logic Program-
vol. 3, no. 2, pp. 61–86; available at http://compscinet. ming into the Future, Springer, 2001; available at
dcs.kcl.ac.uk/OO/PDFPapers/oo030202.pdf.
http://fivedots.coe.psu.ac.th/~ad/papers/summBob.ps.gt.
17. Alferes, J.J. and Pereira, L.M., Logic Programming
5. Davison, A. and Loke, S.W., A Concurrent Logic
Updating: A Guided Approach, in Kakas, A. and
Programming Model of the Web, Tech. Rep. 98/23,
Sadri, F., Eds., Computational Logic: From Logic Pro-
Department of Comput. Sci., Univ. of Melbourne,
gramming into the Future, Essays in Honor of Robert
Kowalski, Springer, 2002, vol. 2, pp. 382–412; available
http://www.cs.mu.oz.au/tr_submit/test/tr_db/mu_TR_
at http://citeseer.nj.nec.com/alferes02logic.html.
18. Dix, J., Furbach, U., and Niemelae, I., Nonmonotonic
6. Mosconi, M. and Porta M., A Visual Approach to Inter-
Reasoning: Towards Efficient Calculi and Implementa-
net Applications Development, Proc. 8th Int. Conf. on
tions, in Voronkov, A. and Robinson, Eds., Handbook ofHuman–Computer Interaction (HCI’99), Munich,
Automated Reasoning, Elsevier, 2001, vol. 2, ch. 18,
1999, vol. 1, pp. 600–604; available at
pp. 1121–1234; available at http://www.cs.man.ac.uk/~
http://vision.unipv.it/research/papers/99p-webappl/
19. Inoue, K., Kawaguchi, S., and Haneda, H., Controlling
7. Kistler, T. and Marais, H., WebL—A Programming
Speculative Computation in Multiagent Environments,
Language for the Web, Elsevier, 1998, pp. 259–270;
Proc. Second Int. Workshop on Computational Logic in
available at http://gatekeeper.research. Multiagent Systems (CLIMA-01), 2001, pp. 9–18; available
compaq.com/pub/DEC/SRC/technical-notes/SRC-1997-
at http://citeseer.nj.nec.com/inoue01controlling.html.
20. Satoh, K. and Yamamoto, K., Speculative Computations
8. Cardelli, L. and Davies, R., Service Combinators for
with Multiagent Belief Revision, Proc. First Int. Joint
Web Computing, Software Engineering, 1999, vol. 25,
Conf. on Autonomous Agents and Multiagent Systems,
no. 3, pp. 309–316; available at http://
Bologna, ACM Press, 2002, pp. 897–904; available at
citeseer.nj.nec.com/cardelli97service.html.
http://agents.umbc.edu/papers/satoh.pdf.
9. Hong, T.W. and Clark, K.L., Concurrent Programming
21. Morozov, A.A. and Obukhov, Yu.V., Actor Prolog: The
on the Web with Webstream, Tech. Rep., Department of
Definition of the Programming Language, Preprint of
Computing, Imperial College, 2000; available at
Inst. of Radio Engineering and Electronics, Russ. Acad.
http://www-lp.doc.ic.ac.uk/~klc/webstream.html. Sci., Moscow, 1996 no. 2(613); the new version of the
10. Zhang, Y. and Keshav, S., WebScript—A Scripting
definition of the language is available at our site
Language for the Web, Tech. Rep., Cotrnell CS Tech.
http://www.cplire.ru/Lab144/index.html.
22. Morozov, A.A., Logic Analysis of Functional Dia-
http://www.research.att.com/~yzhang/papers/webscript-
grams in the Process of Interactive Design of Infor-
mation Systems, Cand. Sci. (Phys.-Mat) Disserta-
11. Barish, G. and Knoblock, C.A., Speculative Execution
for Information Gathering Plans, Proc. 6th Int. Conf. on
http://www.cplire.ru/Lab144/auto.html. AI Planning and Scheduling (AIPS-2002), Toulouse,
23. Morozov, A.A., Actor Prolog: An Object-Oriented
2002; available at http://www.isi.edu/info-
Language with the Classical Declarative Semantics,
Proc. IDL’99 Workshop, Paris, 1999; available at
12. Pontelli, E., Gupta G., ACE: A Logic Language for
http://www.cplire.ru/Lab144/paris.pdf. Intelligent Internet Programming / Department of
24. Morozov, A.A., Obukhov, Yu.V., and Gulyaev, Yu.V.,
Comput. Sci., New Mexico State Univ., Las Cruces,
On The Problem of Using Logic Object-Oriented Pro-
1997; available at http://www.cs.nmsu.edu/lldap/
gramming in the World Wide Web, Proc. Special Rus-sian Session “The Internet Development in Russia”,
13. Tarau, P., Jinni: Intelligent Mobile Agent Program-
First IEEE/Popov Workshop on Internet Technol.
ming at the Intersection of Java and Prolog, Proc. ofand Services, Moscow, 1999, pp. 54–59; available at
PAAM’99, London, 1999; available at http://
http://www.cplire.ru/Lab144/internet.pdf.
citeseer.nj.nec.com/tarau99jinni.html.
25. Morozov, A.A. and Obukhov, Yu.V., On the Problem of
14. Smolka, G., The Oz Programming Model, in van Leeu-
Logical Recognition in the Dynamic Internet Environ-
wen J., Ed., Computer Science Today, LNCS 1000,
ment, Pattern Recognit. Image Anal., 2001, vol. 11,
Springer, 1995, pp. 324–343; available at http://
www.mozart-oz.org/papers/abstracts/volume1000.html.
http://www.cplire.ru/Lab144/pria5.pdf.
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS
26. Morozov, A.A. and Obukhov, Yu.V., An Approach to
Aleksei A. Morozov. Born 1968.
Logic Programming of Intelligent Agents for Searching
and Recognizing Information in the Internet, Pattern Rec-ognit. Image Anal., 2001, vol. 11, no. 3, pp. 570–
582; available at http://www.cplire.ru/Lab144/pria570m.pdf.
degree in Physics and Mathematics in1998. Senior Researcher at the Insti-
27. Morozov, A.A., On Semantic Link Between Logic,
Object-Oriented, Functional, and Constraint Pro-
gramming, Proc. MultiCPL Workshop, Ithaca, USA,
2002; available at http://www.cplire.ru/Lab144/
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003
Some medical conditions require exclusion from school or child care to prevent the spread of infectious diseases among staff and children. This poster provides information on the recommended minimum exclusion periods for infectious conditions and will assist medical practitioners, schools, pre- Exclusion of Contacts1 schools and child care centres Exclusi
MARINE ECOLOGY PROGRESS SERIES Vol. 299: 55–66, 2005 Published September 1 Mar Ecol Prog Ser Impact of recreational harvesting on assemblages in artificial rocky habitats Laura Airoldi1, 2,*, Francesca Bacchiocchi2, Claudia Cagliola2, Fabio Bulleri1, 2, Marco Abbiati2 1 Dipartimento di Biologia Evoluzionistica Sperimentale, Università di Bologna, Via Selmi 3, 40126 Bolo