Results of application of boundary conditions.

## Abstract

This chapter is dedicated to a new knowledge representation model, providing convergence of classical operations research and modern knowledge engineering. Kernel of the introduced model is the recursively generated multisets, selected according to the predefined restrictions and optimization criteria. Sets of multisets are described by the so-called multiset grammars (MGs), being projection of a conceptual background of well-known string-generating grammars on the multisets universum. Syntax and semantics of MGs and their practice-oriented development—unitary multiset grammars and metagrammars—are considered.

### Keywords

- systems analysis
- operations research
- knowledge engineering
- digital economy
- multisets
- recursive multisets
- multiset grammars
- unitary multiset grammars and multimetagrammars
- sociotechnical systems assessment and optimization

## 1. Introduction

Large-scale sociotechnical systems (STS) usually have hierarchical structure, including personnel and various technical devices, which, in turn, consume various material, financial, information resources, as well as energy. As a result, they produce new resources (objects), which are delivered to other similar systems. Main features of such STS are large dimensionality and high volatility of their structures, equipment, consumed/produced objects, and at all, operation logics and dynamics [1, 2, 3, 4, 5].

Knowledge and data representation models, used in STS, provide comparatively easy and comfortable management of very large knowledge and data bases with dynamic structures and content [6, 7, 8, 9, 10]. These model bases are objects other than matrices, vectors, and graphs, traditionally used in operations research and systems analysis [11, 12, 13, 14], and they are much more convenient for practical problem consideration. But, on the other hand, aforementioned models in general case do not incorporate strict theoretical background and fundamental algorithmics, compared with, for example, mathematical programming, which provides strictly optimal solutions for decision-makers. So, practically all decision-support software in the considered STS is based on various heuristics, which correctness and adequacy are not proved usually in the mathematical sense. As a consequence, quality of the adopted decisions, based on such heuristics, in many cases may be far of optimal.

This chapter is dedicated to a primary survey of the developed knowledge representation model, providing convergence of classical operations research and modern knowledge engineering. This convergence creates new opportunities for complicated problem formalization and solution by integrating best features of mathematical programming (strict optimal solution search in solution space, defined by goal functions and boundary conditions) and constraint programming [15, 16, 17] (natural and easily updated top-down representation of logic of the decision-making in various situations). Kernel of the considered model is multisets (MS)—relatively long ago known and in the last 20 years intensively applied object of classical mathematics [18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]. This background is generalized to the recursively generated, or, for short, recursive multisets (RMS) by introduction of so-called multiset grammars, or, again for short, multigrammars (MGs), which were described by the author in [30, 31]. Last, in turn, are peculiar “projection” of the conceptual basis of classical formal grammars by Chomsky [32, 33], operating strings of symbols, to the multisets universum in such a way, that MGs provide generation of one multiset from another and selection (filtration) of those, which satisfy necessary integral conditions: boundary restrictions and/or optimality criteria.

MGs may be considered as prolog-like constraint programming language for solution of problems in operations research and systems analysis areas. Taking into account relative novelty of the multigrammatical approach and absence of any substantial associations with mathematical constructions presented lower, we introduce main content of the chapter by short informal description of the main elements of this approach in Section 2. Basic formal definitions are presented in Section 3. Section 4 is dedicated to multiset grammars, while Section 5—to detailed consideration of the so-called unitary multigrammars (UMGs) and unitary multimetagrammars (UMMGs), which are main tool of the aforementioned problem formalization and solution.

## 2. Informal description

Let us consider a company, which consists of director, three departments, and one separate laboratory. This fact may be simply represented as follows:

In this notation, a whole structure of the company, detailed to employee positions, may be described in such a way:

This set of constructions is of the form:

describes following set, created by multiplying and summarizing quantities of identical positions:

where

Let us join to the company structure knowledge about employees’ month salary, represented in the same unified manner:

After applying to the joined set of constructions just the same multiplying-summarizing procedure, we may obtain resulting set containing the only element {100,000*eur*}, which defines company’s total financial resource, necessary for employees’ provision a month.

Presented knowledge representation concerns systems analysis, that is, obtaining integral parameters of the system given its structure and local parameters.

Consider more sophisticated task-relating systems design and concerning development of company structure given its integral parameters. Goal is to determine rational quantity of departments and laboratories in the department, as well as quantities of analysts and assistants in one laboratory. Total salary is no more than 120,000 eur, quantity of analysts in one laboratory may be from 1 to 3, while corresponding quantity of assistants may be from 2 to 6. Total quantity of employees must be maximal. There may be three different variants of company structure: (1) three departments and one laboratory; (2) two departments and three laboratories; and (3) four departments. Corresponding set of constructions is as follows:

Constructions, defining employees’ salary, and other aforementioned restrictions are as follows (for definiteness, let us take that quantity of laboratories in one department does not exceed five):

As seen, along with already introduced “detailing” constructions, there are additional constructions, defining sets of values of variables, having places in the first ones, as well as conditions, determining optimization criterion (there may be several such criteria), and bounds of quantities of some objects in the resulting sets. Evidently, due to presence of alternatives in the description of company structure (there are three such alternatives) and variables in some of “detailing” constructions, there may be more than one resulting set like Eq. (4). These sets are of the form *x* is the quantity of employees, while *y*—total salary, corresponding to this variant. Conditions (16)–(20) provide selection of those sets, which satisfy them in the described sense. In general, Eqs. (16)–(20) may be interpreted as a query, determining subset of all possible variants, described by Eqs. (6)–(15).

To “mark” “detailing” constructions, used while resulting set creation, one can add to their “bodies” elements like

If so, then resulting sets will be of the form:

To implant to these sets values of variables, it is sufficient to represent them in resulting sets in “usual” form *j* is its value, so considered example will lead us to sets like:

As seen, shortly introduced by this example knowledge and query representation language, being easy to understand and to use, allows formalization of multicriterial optimization problems, for years associated with mathematical programming. On the other hand, “detailing” constructions have form of productions (rules), far and wide used in knowledge engineering and being common background of prolog-like declarative (nonprocedural) knowledge representation [34, 35, 36]. As will be shown lower, such constructions may be used not only for structuring, but in many other cases, enabling description of various systems behavior and interaction, as well as their mutual impacts. For such reasons, this informally described technique is taken as a basis for the description of the developed mathematical toolkit considered thoroughly in the following sections.

## 3. Basic operations on multisets

Classical set theory is based on the concept of set as unordered assembly of elements, different from one another. Theory of multisets assumes presence of equal (“indistinguishable”) elements:

Expression (26) is recorded as:

where

Fact that object

There are five main operations on multisets, used lower: join, intersection, addition, subtraction, and multiplication by constant [26, 27].

Consider two multisets:

Result of their join (recorded as

where

Result of

Result of

Result of

At last, result of *n* (recorded as

(here integers’ usual multiplication is recorded as

There are also two basic relations on multisets: inclusion (

Multiset *v* is included to multiset

and multiset *v* is strictly included to multiset

**Example 1.** Let

All defined operations are known from widespread sources (e.g., aforementioned [26, 27]). At the same time, filtering operations, defined lower, operate sets of multisets (SMS), creating subsets of these sets by selection of multisets, which satisfy some conditions, being operands of these operations.

There are two types of conditions: boundary and optimizing.

Boundary condition may be elementary or concatenated (for short, “chain”). Elementary boundary condition (EBC) may have one of the following forms:

where *n* is the integer number, and

where

EBC semantics is following. Let *V* be set of multisets, and *v* satisfies EBC *v* satisfies EBC *v* satisfies EBC

CBC semantics is defined as follows. CBC (39) is replaced by CBC sequence

and

Result of application of boundary condition *b* to SMS *V* is recorded as

**Example 2.** Let *V*.

Optimizing condition has form *a = opt,* where *a* is the object, and *n* in multiobject *n* in multiobject

Filter is join of boundary

where

where

and

**Example 3.** Consider set

Let

where

Filtration is performed as follows:

Due to commutativity of set-theoretic join and intersection operations, filtration inside subfilters may be executed in the arbitrary order.

## 4. Multiset grammars

As mentioned higher, multiset grammars are tool, providing generation of one multisets from another, or, what is the same, generation sets of multisets.

By analogy with classical grammars, operating strings of symbols [32, 33], we shall define multigrammar as a couple.

where *R*, called scheme, is finite set of the so-called rules, which are used for generation of new multisets from already generated. Rule has the form:

where

Speaking informally, if

Set of multisets, defined by MGs *S*, is the following:

where

As seen, function (53) implements application of rule *i +* 1-th step of generation, new SMS is formed by application of all rules

*i*

**Example 4.** Let

As seen,

(for short, identical parts of different generation chains are omitted). So

By analogy with classical string-generating grammars, multigrammars may be context-sensitive and context-free (CF). In the last one, left parts of all rules have form

## 5. Unitary multiset grammars and metagrammars

Start point for unitary multigrammars (UMGs), developed on the considered basis, is simplified representation of CF rules: instead of

they are written as:

Construction (56) is called unitary rule (UR), object *a*—its head, and unordered sequence (list)

Let us consider UMG formal definition and illustrating example. Unitary multigrammar is couple *a* is the so-called title object, and *R*, as in multigrammars, is scheme—set of unitary rules (56).

Iterative representation of UMG semantics, i.e., generation of SMS

where

Here, *R* does not include URs, which head is *a* (i.e., *a* has place only in the UR bodies). *R* of UMG *S*. Multiset, generated by UMG *S*, all objects of which are terminal, is also called terminal multiset (as seen, this notion of TMS does not contradict to the defined higher regarding MGs). In Eq. (61), UR

As seen, Eq. (59) defines *S*,—while Eq. (60) by condition

**Example 5.** Consider unitary multigrammar *R* includes following unitary rules:

Filtering unitary multigrammars (FUMGs) are UMG generalization, providing generation of terminal multisets and selection those of them, which satisfy conditions, assembled to filters, which were described higher in Section 3.

FUMGs are triple *, R*, and *F* have the same sense, as above, and set of terminal multisets, generated by *S*, is defined as follows:

that is, set of terminal multisets, generated by *S*, is result of filtering STMS, generated by UMGs *F*.

**Example 6.** Let *R* is as in Example 5, while

Filtering unitary multigrammars are, in turn, basis for unitary multiset metagrammars, or, for short, multimetagrammars, which are considered at all the rest part of the chapter and are main toolkit for the description and solution of the optimization problems, mentioned in the introduction.

Unitary multimetagrammar *S* is, as higher, triple *R* is the scheme, containing unitary rules and so-called unitary metarules (UMR), while *F* is the filter. Consider UMMG syntax and semantics.

Unitary metarule has the form:

where *a* in Eq. (55) is called head, while

Filter *F* is set of conditions, which may be of the following forms:

where *F* includes subfilter *R*, instead of multiplicities-variables being in their bodies; unitary rules, already having place in *R*, are transferred to new scheme, denoted

Coming back to Section 2, one can see that Eqs. (6)–(20) are set of elements of unitary metamultigrammar: Eqs. (6)–(8) and Eqs. (11)–(15) are unitary rules, Eqs. (9)–(10) are unitary metarules, Eq. (16) is optimizing condition, Eq. (17) is boundary condition, while Eqs. (18)–(20) are variable declarations. As seen,

so, this one UMMG, consisting of 15 lines, replaces

Let us now give strict definition of unitary multimetagrammar notion. UMMG

and, at last, if *r* is

where

As seen, according to Eqs. (75) and (76), all multiplicities-variables of unitary metarule **N**) remain unchanged. Evidently, if all

Let us note, that multiplicities-variables area of actuality is whole UMMG scheme, that is, if there are *n* > 1 occurrences of one and the same variable

**Example 7.** Let us consider UMMG *R* contains following three unitary metarules:

and filter *F* includes following conditions, the first being boundary, the second—optimizing, while the last two—variable declarations:

According to Eqs. (70)–(76), this UMMG defines four UMGs:

where

(URs are represented in angle brackets for unambiguity). These UMGs define, respectively, following sets of terminal multisets:

As may be seen, Eqs. (64)–(66) define boundary conditions, concerning objects and variables, and optimizing conditions, concerning only objects, that is why from both theoretical and practical points of view, it is reasonable to extend UMMG filters by optimizing conditions, relating variables. By analogy with Eq. (65), such conditions will have the form:

This form defines optimality of the generated terminal multisets through multiplicity-variable values, used while these TMS generation. Eq. (77) semantics is quite clear: select those TMS, which are generated by the help of value of variable

Most simple formal definition of the verbally described sense of Eq. (77) optimizing condition may be as follows. Let us introduce *l* auxiliary terminal objects

to scheme *R*, thus creating scheme *R*, and substituting all optimizing conditions of the form *F*, thus converting them to the “canonical” form (65)—remember, *R*. Obtained filter will be denoted as

As seen now, UMMG

where

and TMS (79) will be selected to *F* and concerning terminal objects

It is not difficult to define *S*: it is clear that all

**Example 8.** As may be seen, problem, described in Section 2, is to obtain *m* quantity of laboratories, as well as *n* and *l* quantities of analysts and assistants, respectively, in one laboratory. Although Eqs. (18)–(20) do not contain optimizing conditions of the form

is much more useful than TMS like {100*employee,* 115,000*eur*} because of Eq. (81) with greater informativity (here, we use *m, n, l* instead of

So we shall use *R* does not include variable-containing optimizing conditions.

To finish with syntax and semantics of UMGs/UMMGs, let us note that class of unitary multigrammars is strict subclass of filtering unitary multiset grammars (UMGs

UMG/UMMG algorithmics and applications are considered in the separate chapter of this book.