Introduction

Insertion modeling is the approach to modeling complex distributed systems based on the theory of interaction of agents and environments [1][2][3]. Mathematical foundation of this theory was presented in [4]. During the last decade insertion modeling was applied to the verification of requirements for software systems [5][6][7][8][9].

First time the theory of interaction of agents and environments was proposed as an alternative to well known theories of interaction such as Milner's CCS [10] and pi-calculus [11], Hoare's CSP [12], Cardelli's mobile ambients [13] and so on. The idea of decomposition of a system to a composition of environment and agents inserted into this environment implicitly exists in all theories of interaction and for some special case it appears explicitly in the model of mobile ambients.

Another source of ideas for insertion modeling is the search of universal programming paradigms such as Gurevich's ASM [14], Hoare's unified theories of programming [15], rewriting logic of Meseguer [16]. These ideas were taken as a basis for the system of insertion programming [17] developed as the extension of algebraic programming system APS [18]. Now this system initiated the development of insertion modeling system IMS which started in Glushkov Institute of Cybernetics. The development of this system is based on the version of APS enhanced by the former student of the author V.Peschanenko. The first version of IMS and some simple examples of its use are available from [19].

To implement the insertion model in IMS one must develop insertion machine with easily extensible input language, the rules to compute insertion functions and a program of interpretation and analyzing of insertion models. The architecture, input languages and examples of insertion machines and insertion modeling system are considered in the paper.

The Architecture of Insertion Modeling System

Insertion modeling system is an environment for the development of insertion machines and performing experiments with them. The notion of insertion machine was first introduced in [17] and it was used as a tool for programming with some special class of insertion functions. Later this notion was extended for more wide area of applications, different levels of abstraction, and multilevel structures.

Insertion model of a system represent this system as a composition of environment and agents inserted into it. Contrariwise the whole system as an agent can be inserted into another environment. In this case we speak about internal and external environment of a system. Agents inserted into the internal environment of a system themselves can be environments with respect to their internal agents. In this case we speak about multilevel structure of agent or environment and about high level and low level environments.

As usually, insertion function is denoted as E[u] were E is the state of environment and u is the state of an agent (agent in a given state). E[u] is a new environment state after insertion an agent u. So, the expression

E[u[v], F [x, y, z]]

denotes the state of a two level environment with two agents inserted into it. At the same time E is an external environment of a system F [x, y, z] and F is an internal environment of it. All agents and environments are labeled or attributed transition systems (labeled systems with states labeled by attribute labels [9]). The states of transition systems are considered up to bisimilarity. This means that we should adhere to the following restriction in the definition of states: if

E ∼ B E and u ∼ B u then E[u] ∼ B E [u ].

The main invariant of bisimilarity is the behavior beh(E) of transition system in the state E (an oriented tree with edges labeled by actions and nodes labeled by attribute labels). Therefore the restriction above can be written as follows:

beh(E) = beh(E ) ∧ beh(u) = beh(u ) ⇒ beh(E[u]) = beh(E [u ])

Behaviors themselves can be considered as states of transition systems. If the states are behaviors then the relation above is valid automatically, because in this case beh(E) = E, beh(u) = u. Otherwise the correctness of insertion function must be proved in addition to its definition. In any case we shall identify the states with the corresponding behaviors independently from their representation.

To define finite behaviors we use the language of behavior algebra (a kind of process algebra defined in [4]). This algebra has operation of prefixing, nondeterministic choice, termination constants (∆, 0, ⊥) and approximation relation. For attributed transition systems we introduce the labeling operator for behaviors. To define infinite behaviors we use equations in behavior algebra. Usually these equations have the form of recursive definitions u i = F i (u), i ∈ I. Left hand sides of these definitions can depend on parameters u i (x i ) = F i (u, x), i ∈ I. To define the attribute labels we use the set of attributes, symbols taking their values in corresponding data domains. These attributes constitute a part of a state of a system and change their values in time. All attributes are devided to external (observable) and internal (nonobservable). By default the attribute label of a state is the set of values of all observable attributes for this state.

The general architecture of insertion machine is represented on the fig. 1.

Fig. 1. Architecture of Insertion Machine

The main component of insertion machine is model driver, the component which controls the machine movement along the behavior tree of a model. The state of a model is represented as a text in the input language of insertion machine and is considered as an algebraic expression. The input language include the recursive definitions of agent behaviors, the notation for insertion function, and possibly some compositions for environment states. The state of a system must be reduced to the form E[u 1 , u 2 , . . . ]. This functionality is performed by the module called agent behavior unfolder. To make the movement, the state of environment must be reduced to the normal form i∈I a i .E i + ε where a i are actions, E i are environment states, ε is a termination constant. This functionality is performed by the module environment interactor. It computes the insertion function calling if it is necessary the agent behavior unfolder. If the infinite set I of indices in the normal is allowed, then the weak normal form a.F + G is used, where G is arbitrary expression of input language.

Two kinds of insertion machines are considered: real type or interactive and analytical insertion machines. The first ones exist in the real or virtual environment, interacting with it in the real or virtual time. Analytical machines intended for model analyses, investigation of its properties, solving problems etc. The drivers for two kinds of machines correspondingly are also divided on interactive and analytical drivers.

Interactive driver after normalizing the state of environment must select exactly one alternative and perform the action specified as a prefix of this alternative. Insertion machine with interactive driver operates as an agent inserted into external environment with insertion function defining the laws of functioning of this environment. External environment, for example, can change a behavior prefix of insertion machine according to their insertion function. Interactive driver can be organized in a rather complex way. If it has criteria of successful functioning in external environment intellectual driver can accumulate the information about its past, develop the models of external environment, improve the algorithms of selecting actions to increase the level of successful functioning. In addition it can have specialized tools for exchange the signals with external environment (for example, perception of visual or acoustical information, space movement etc.).

Analytical insertion machine as opposed to interactive one can consider different variants of making decision about performed actions, returning to choice points (as in logic programming) and consider different paths in the behavior tree of a model. The model of a system can include the model of external environment of this system, and the driver performance depends on the goals of insertion machine. In the general case analytical machine solves the problems by search of states, having the corresponding properties(goal states) or states in which given safety properties are violated. The external environment for insertion machine can be represented by a user who interacts with insertion machine, sets problems, and controls the activity of insertion machine.

Analytical machine enriched by logic and deductive tools can be used for symbolic modeling. The state of symbolic model is represented by means of properties of the values of attributes rather then their concrete values.

General architecture of insertion modeling system is represented on fig. 2. High level model driver provides the interface between the system and external environment including the users of the system. Design tools based on algebraic programming system APS are used for the development of insertion machines and model drivers for different application domains and modeling technologies. Verification tools are used for the verification of insertion machines, proving their properties statically or dynamically. Dynamic verification uses generating symbolic model traces by means of special kinds of analytical model drivers and deductive components.

The repository of insertion machines collects already developed machines and their components which can be used for the development of new machines as their components or templates for starting. Special library of APLAN functions supports the development and design in new projects. The C++ library for IMS supports APLAN compilers and efficient implementation of insertion machines. Deductive system provides the possibility of verification of insertion models. <functional expression> <named agent behavior>::=<agent name>:<behavior> Therefore, the language of behavior algebra (termination constants, prefixing and nondeterministic choice) is extended by functionals expressions and explicit representation of insertion function. The syntax and semantics of actions, environment states, and functional expressions are defined in the environment description. We shall not consider all possibilities and details of environment description language restricting ourselves by making only some necessary comments.

First of all note, that all main components of behavior algebra language (actions, environment states, and functional expressions) are algebraic or logic expressions of base language (terms and formulas). This language is a multisorted (multitype) first order logic language. The signature of this language is defined in the environment description. Functional and predicate symbols can be interpreted and uninterpreted. Interpreted symbols have fixed domains and interpretations given by algorithms of computing values or reducing to canonical forms. All uninterpreted symbols have types and their possible interpretations are restricted by definite domains and ranges. Uninterpreted functional symbols are called attributes. They represent the changing part of the environment. Attributes of arity 0 are called simple attributes, others are called functional ones. Predicates are considered as functions ranging in Boolean type {0, 1}. If an attribute f has functional type (τ 1 , τ 2 , . . .) → τ then attribute expressions f (t 1 , t 2 , . . .) are available for all other expressions.

Examples of Insertion Machines

The simplest insertion machines are machines for parallel and sequential insertion. Insertion function is called sequential if E[u, v] = E[u; v] where ";" means sequential composition of behaviors. Special case of sequential insertion is a strong sequential composition: E[u] = (E; u). This definition assumes that actions of agents and environment are the same and environment is defined by its behaviors. The sequentiality of this composition follows from associativity of sequential composition of behaviors.

Example of insertion machine with strong sequential insertion is represented on fig. 3

Fig. 3. Example of Strong Sequential Insertion

The function seq is a function from IMS library that defines the sequential composition of behaviors:

(u; v) = u a →u a.(u ; v) + u=u+ε (ε; v), (0; v) = 0, (∆; v) = v, (⊥; v) = ⊥

The function unfold reduces the behavior expression to normal form a i .u i +ε. This insertion machine generates a word c n a m with nondeterministically chosen m, n ≥ 0 and successfully terminates. We can define as the condition for the goal state the equality m = n and the driver for this machine will terminate on traces c n a n .

An example of sequential (not strong) insertion is shown on fig. 4.

Model

Fig. 4. Model of Simple Imperative Language

This example is a model of simple imperative language and can be considered as insertion representation of its operational semantics.

Insertion function is called a parallel insertion function if

E[u, v] = E[u v]. Special case of parallel composition is a strong parallel insertion:E[u] = E u].

As in the case of strong sequential composition this definition assumes that actions of environment and agents are the same. Example of a model with strong parallel insertion is presented on the fig. 5. Functions synchr, lmrg, and delta from IMS library are used for definition of parallel composition. Their meaning can be define by the following formulas: synchr(x, y) =

Restrictions on Insertion Functions

The most typical restriction is additivity. Insertion function is called additive if

E[u+v] = E[u]+E[v], (E +F )[u] = E[u]+F [u].

Another restriction, which allow to reduce the number of considered alternatives when behaviors are analyzed is the commutativity of insertion function:

E[u, v] = E[v, u].

Especially the parallel insertion is a commutative one. Some additional equations: 0

[u] = 0, ∆[u] = u, ⊥[u] = bot.

The state of environment is called indecomposable if from E = F [u] it follows that E = F and u = ∆. Equality means bisimilarity. The set of all indecomposable states constitutes the kernel of a system. Indecomposable states (if they exist) can be considered as states of environment without inserted agents. For indecomposable states usually the following equations hold:

E[0] = 0, E[∆] = E, E[⊥] = ⊥.

In [3] the classification of insertion functions was presented: one-step insertion, head insertion, and look-ahead insertion. Later we shall use insertion functions with the following main rule:

E a → E , α : u b → β : u E[α : u] c → E [β : u ] , P (E, a, α, b, β, c),

where P is a continuous predicate. Continuous means that the value of this predicate depends only on some part of behavior tree in the environment state E, which has a finite height (prefix of the tree E of finite height). Hereby, this rule refers to a head insertion. The rules for indecomposable environment states and for termination constants should be added to the main rule.

The next rule

E a → E , u b → β : u E [u] c → E [u ] , P (E, a, c),

is the particular case for the head insertion rule in combination with additivity and parallel insertion or commutativity requirements. Such rule will be named permitted rule. It could be interpreted by as follows: agent can execute the action a, and environment permits to execute this action. Predicate E for permitted rule will be named permitted predicate.

Constraint Programming

Constraint programming is a powerful paradigm for solving combinatorial search problems that draws on a wide range of techniques from artificial intelligence, computer science, databases, programming languages, and operations research. Constraint programming is currently applied with success to many domains, such as scheduling, planning, vehicle routing, configuration, networks, and bioinformatics [24].

The Constraint programming paradigm has some resemblance to traditional Operations Research (OR) approach, in that the general path to a solution is:

1. analyzing the problem to solve, in order to understand clearly which are its parts; 2. determining which conditions(relationships) hold among those parts: these relationships and conditions are key to the solving, for they will be used to model the problem; 3. stating such conditions(relationships) as equations; to achieve this step not only the right variables and relationships must be chosen: as we will see, Constraint programming usually offers a series of different constraint systems, some of which are better suited than others for a given task; 4. setting up these equations and solving them to produce a solution; this is usually transparent to the user, because the language itself has built-in solvers [25].

There are, however, notable differences with OR, mainly in the possibility of selecting different domains of constraints, and in the dynamic, generation of those constraints. This seamless combination of programming and equation solving accounts for some of the unique components of Constraint Programming:

the use of sound mathematical methods: well-known and proved algorithms are provided as intrinsic, builtin components of Constraint programming languages and tools; the provision of means to perform programmed search, especially in Constraint programming (were search is implicit in language itself);

the possibility of developing modular, hybrid models, when necessary: many Constraint programming systems offer different constraint systems, which can be combined to model the various parts of the problem using the tool more adequate for them; the flexibility provided by the programming language used, which allows the programmer to create the equations to be solved dynamically, possibly depending on the input data.

As with any other computational approach, all problems are amenable to be tackled with Constraint programming; notwithstanding, there are some types of problems which can be solved with comparatively little effort using Constraint programming based tools. Those applications share some general characteristics:

-No general, efficient algorithms exist (NP-completeness): specific techniques (heuristics) must be used. These are usually problems with a heavy combinatorial part, and enumerating solutions is often impractical altogether. A fast program using usual programming paradigms is often too hard and complicated to produce, and normally it is so tied to the particular problem that adapting it to a related problem is not easy. -The problem specification has a dynamic component: it should be easy to change programs rapidly to adapt. This has points in common with the previous item: Constraint programming tools have builtin algorithms which have been tuned to show good behavior in a variety of scenarios, so updating the program to new conditions amounts to changing the setting up of the equations. -Decision support required: either automatically in the program or in cooperation with the user. Many decisions can be encoded in mathematical formulae, which appear as rules and which are handled by the internal solvers, so (although, of course, not always) there is no need to program explicit decision trees [26].

Among the applications with these characteristics, the following may be cited: planning, scheduling, resource allocation, logistics, circuit design and verification, finite state machines, financial decision making, transportation, spatial databases, etc.

Insertion Machine for Constraint Programming

Some example of insertion machines and restrictions for insertion function are in [3,9,23]. In this section we try to show how to use insertion modelling for constraint programming [26]. The problems of constraint programming, where a main goal is behavior of the system, is the closest to the insertion modelling. For example, the problem of wolf-goat-cabbage [27] (A farmer wishes to transfer (by boat) a wolf, a goat, and a cabbage from the left bank of a river to the right bank. If left unsupervised, the wolf will eat the goat and the goat will eat the cabbage, but nothing will happen as long as the farmer is near. Beside the farmer there is only a place for one item in the boat).

Let's consider a formalization of this problem in insertion modelling. Let E be the next enviroment: obj( constraints : rs(x, y, z)( obj(W olf : lef t, Goat : lef t, x, F erryman : right) = 0, obj(W olf : right, Goat : right, x, F erryman : lef t) = 0, obj(x, Goat : lef t, Cabbage : lef t, F erryman : right) = 0, obj(x, Goat : right, Cabbage : right, F erryman : lef t) = 0, obj(W olf : z, x, y, F erryman : z) = 1, obj(x, Goat : z, y, F erryman : z) = 1, obj(x, y, Cabbage : z, F erryman : z) = 1 ); initial : obj( W olf : lef t, Goat : lef t, Cabbage : lef t, F erryman : lef t ) ) where initial is initial state where all creatures are in left bank of the river, constraits are constraint equations with right part of 0 define non possible cases (0 is the neutral element of non-deterministic choice + of insertion modeling) and with 1 if ferryman could transport thous creatures in that case. These both values are covered by two different states of ferry: 1 is just before ferry and 0after.

The coresponded input data could be defined in the following way: (f erry W olf f erry Goat f erry Cabbage).assetion constraints So, the transition relation of the system is defined in fig. 6. Insertion modelling system has found 1 goal trace -all creatures are in other coast and 10 visited traces -those traces cover all possible behaviors of such system.

ϕ [p] f erry x − −−−− → ϕi [p] , constraints(ϕ) = 1 ϕ [p] f erry x − −−−− → 0, constraints(ϕi) = 0 ∨ ¬constraints(ϕ) = 1 ϕ [p]

Typically IMS generated trace is defined by user. It could look like sequance of actions or environment states etc. For this example, to simplify the view of the traces we propose to use one uninterpreted action transport: transport(¬(c = ϕ i .F erryman), F erryman, x), where operation . returns state of the ferryman and ¬ returns other coast. So, goal state trace has the next view: where init is the initial state and N il means that ferryman is ferried along. In general case, insertion machine for constraint programming should use:

1. assetion constraints agents action in agent behaviour and initial state. 2. Environment description should have non empty section constraints.

Conclusion

The main concepts of insertion modeling system has been considered in the present paper. The system was successfully used for the development of prototypes of the tools for industrial VRS (Verification of Requirement Specification) system and research projects in Glushkov Institute of Cybernetics. Now it is used for the development of program verification tool and 'verifiable programming' project, and for constraint programming. The system continues its enhancement and new features are added while developing new projects. The far goal in the developing of IMS consists of getting of sufficiently rich cognitive architecture to its basis, which could be used in the artificial intelligence research.