Multiset-Based Knowledge Representation for the Assessment and Optimization of Large-Scale Sociotechnical Systems

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.

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:

$$\mathit{\text{company}}\to 1\cdot \mathit{\text{director}},3\cdot \mathit{\text{department}},1\cdot \mathit{\text{laboratory}}.$$ E1

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

$$\begin{array}{l}\mathit{\text{department}}\to 1\cdot \mathit{\text{head}}-\mathit{\text{department}},3\cdot \mathit{\text{laboratory}},\\ \mathit{\text{laboratory}}\to 1\cdot \mathit{\text{head}}-\mathit{\text{laboratory}},2\cdot \mathit{\text{analyst}},3\cdot \mathit{\text{assistant}}.\end{array}$$ E2

This set of constructions is of the form:

$$a\to n_1\cdot a_1,\dots ,n_m\cdot a_m$$ E3

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

$$\left\{1\cdot \mathit{\text{director}},3\cdot \mathit{\text{head}}-\mathit{\text{department}},10\cdot \mathit{\text{head}}-\mathit{\text{laboratory}},20\cdot \mathit{\text{analyst}},30\cdot \mathit{\text{assistant}}\right\},$$ E4

where $n_i\cdot a_i$ means there are $n_i$ positions of type $a_i$ in this company.

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

$$\begin{array}{l}\mathit{\text{director}}\to 10000\cdot \mathit{eur},\\ \mathit{\text{head}}‐\mathit{\text{department}}\to 5000\cdot \mathit{eur},\\ \mathit{\text{head}}‐\mathit{\text{laboratory}}\to 3000\cdot \mathit{eur},\\ \mathit{\text{analyst}}\to 1500\cdot \mathit{eur},\\ \mathit{\text{assistant}}\to 500\cdot \mathit{eur}.\end{array}$$ E5

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 $\cdot$ 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:

$$\mathit{\text{company}}\to 1\cdot \mathit{\text{director}},3\cdot \mathit{\text{department}},1\cdot \mathit{\text{laboratory}},$$ E6

$$\mathit{\text{company}}\to 1\cdot \mathit{\text{director}},2\cdot \mathit{\text{department}},1\cdot \mathit{\text{laboratory}},$$ E7

$$\mathit{\text{company}}\to 1\cdot \mathit{\text{director}},4\cdot \mathit{\text{department}},$$ E8

$$\mathit{\text{department}}\to 1\cdot \mathit{\text{head}}‐\mathit{\text{department}},m\cdot \mathit{\text{laboratory}},$$ E9

$$\mathit{\text{laboratory}}\to 1\cdot \mathit{\text{head}}‐\mathit{\text{laboratory}},n\cdot \mathit{\text{analyst}},l\cdot \mathit{\text{assistant}}.$$ E10

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):

$$\mathit{\text{director}}\to 1\cdot \mathit{\text{employee}},10000\cdot \mathit{eur},$$ E11

$$\mathit{\text{head}}‐\mathit{\text{department}}\to 1\cdot \mathit{\text{employee}},5000\cdot \mathit{eur},$$ E12

$$\mathit{\text{head}}‐\mathit{\text{laboratory}}\to 1\cdot \mathit{\text{employee}},3000\cdot \mathit{eur},$$ E13

$$\mathit{\text{analyst}}\to 1\cdot \mathit{\text{employee}},1500\cdot \mathit{eur},$$ E14

$$\mathit{\text{assistant}}\to 1\cdot \mathit{\text{employee}},500\cdot \mathit{eur},$$ E15

$$\mathit{\text{employee}}=\text{max},$$ E16

$$\mathit{eur}\le 120000,$$ E17

$$1\le m\le 5,$$ E18

$$1\le n\le 3,$$ E19

$$1\le l\le 6.$$ E20

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 $\left\{x\cdot \mathit{\text{employee}},y\cdot \mathit{eur}\right\}$ , where 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 $1\cdot \mathit{variant}‐\mathrm{i}$ , for example,

$$\mathit{\text{company}}\to 1\cdot \mathit{variant}‐\mathit{1},1\cdot \mathit{\text{director}},3\cdot \mathit{\text{department}},1\cdot \mathit{\text{laboratory}},$$ E21

$$\mathit{\text{company}}\to 1\cdot \mathit{variant}‐2,1\cdot \mathit{\text{director}},2\cdot \mathit{\text{department}},3\cdot \mathit{\text{laboratory}},$$ E22

$$\mathit{\text{company}}\to 1\cdot \mathit{variant}‐3,1\cdot \mathit{\text{director}},4\cdot \mathit{\text{department}}.$$ E23

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

$$\left\{1\cdot \mathit{variant}‐\mathrm{i},\mathrm{x}\cdot \mathit{\text{employee}},y\cdot \mathit{eur}\right\}.$$ E24

To implant to these sets values of variables, it is sufficient to represent them in resulting sets in “usual” form $j\cdot v$ , where $v$ is variable and j is its value, so considered example will lead us to sets like:

$$\left\{1\cdot \mathit{variant}‐\mathrm{i},\mathrm{x}\cdot \mathit{\text{employee}},y\cdot \mathit{eur},i\cdot m,j\cdot n,k\cdot l\right\}.$$ E25

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:

$$v=\left\{\underset{n_1\mathit{\text{times}}}{\underbrace{a_1,\dots ,a_1}},\dots ,\underset{n_i\mathit{\text{times}}}{\underbrace{a_i,\dots ,a_i}},\dots ,\underset{n_m\mathit{\text{times}}}{\underbrace{a_m,\dots ,a_m}}\right\}$$ E26

Expression (26) is recorded as:

$$v=\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\},$$ E27

where $v$ is called multiset, $a_1,\dots ,a_m$ —objects, $n_1,\dots ,n_m$ —multiplicities of these objects, and $n_1\cdot a_1,\dots ,n_m\cdot a_m$ —multiobjects. Following Eq. (27), one may consider $v$ as set of multiobjects; also, from substantial point of view, set $\left\{a_1,\dots ,a_m\right\}$ and multiset $\left\{1\cdot a_1,\dots ,1\cdot a_m\right\}$ are equivalent. Empty multiset, as well as empty set, is designated as $\left\{\varnothing \right\}$ . Multiplicity of object may be zero, what is equivalent to absence of this object in the multiset:

$$\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m,0\cdot a_{m+1}\right\}=\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\}.$$ E28

Fact that object $a$ or multiobject $n\cdot a$ belongs to multiset $v$ (“enters $v$ ”) is designated by one and the same symbol $\in :a\in v,n\cdot a\in v$ . Set $\beta \left(v\right)=\left\{a|n\cdot a\in v\right\}$ is called basis of multiset $v$ .

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

Consider two multisets:

$$\begin{array}{l}v=\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\},\\ v^{\prime }=\left\{n_1^{\prime }\cdot a_1^{\prime },\dots ,n_{m^{\prime }}^{\prime }\cdot a_{m^{\prime }}^{\prime }\right\}.\end{array}$$ E29

Result of their join (recorded as $\mathbf{\cup }$ ) is multiset.

$$\begin{array}{l}v\bigcup v^{\prime }=\left(\bigcup _{\underset{\begin{array}{l}n\cdot a\in v\\ n^{\prime }\cdot a\in v\end{array}}{a\in \left\{a_1,\dots ,a_m\right\}\cap \left\{a_1^{\prime },\dots ,a_{m^{\prime }}^{\prime }\right\}}}\left\{\text{max}\left(n,n^{\prime }\right)\cdot a\right\}\right)\cup \\ \cup \left(\bigcup _{\underset{n\cdot a\in v}{a\in \left\{a_1,\dots ,a_{m^{\prime }}^{\prime }\right\}-\left\{a_1^{\prime },\dots ,a_{m^{\prime }}^{\prime }\right\}}}\left\{n\cdot a\right\}\right)\cup \\ \cup \left(\bigcup _{\underset{n^{\prime }\cdot a^{\prime }\in v}{a^{\prime }\in \left\{a_1^{\prime },\dots ,a_m^{\prime }\right\}-\left\{a_1,\dots ,a_m\right\}}}\left\{n^{\prime }\cdot a^{\prime }\right\}\right),\end{array}$$ E30

where $\cup ,\cap \text{and}-$ designate operations of set-theoretical join, intersection, and subtraction of two sets correspondingly, while $\bigcup$ designates operation of set-theoretical join of sets determined by underwritten conditions.

Result of $v,v^{\prime }$ multisets intersection (recorded as $\bigcap$ ) is multiset.

$$v\bigcap v^{\prime }=\left(\bigcup _{{\displaystyle \underset{\begin{array}{l}n\cdot a\in v\\ n^{\prime }\cdot a\in v\end{array}}{a\in \left\{a_1,\dots ,a_m\right\}\cap \left\{a_1^{\prime },\dots ,a_{m^{\prime }}^{\prime }\right\}}}}\left\{\text{min}\left(n,n^{\prime }\right)\cdot a\right\}\right).$$ E31

Result of $v,v^{\prime }$ multisets addition (recorded as bold $\mathbf{+}$ ) is multiset.

$$\begin{array}{l}v\mathbf{+}{v}^{\prime }=\left(\bigcup _{\underset{\begin{array}{l}n\cdot a\in v\\ n^{\prime }\cdot a\in v\end{array}}{a\in \left\{a_1,\dots ,a_m\right\}\cap \left\{a_1^{\prime },\dots ,a_{m^{\prime }}^{\prime }\right\}}}\left\{\left(n+n^{\prime }\right)\cdot a\right\}\right)\cup \\ \cup \left(\bigcup _{\underset{n\cdot a\in v}{a\in \left\{a_1,\dots ,a_m\right\}-\left\{a_1^{\prime },\dots ,a_{m^{\prime }}^{\prime }\right\}}}\left\{n\cdot a\right\}\right)\cup \\ \cup \left(\bigcup _{\underset{n^{\prime }\cdot a\in v^{\prime }}{a^{\prime }\in \left\{a_1^{\prime },\dots ,a_{m^{\prime }}^{\prime }\right\}-\left\{a_1,\dots ,a_m\right\}}}\left\{n^{\prime }\cdot a\right\}\right).\end{array}$$ E32

Result of $v^{\prime }$ multiset subtraction from $v$ multiset (recorded as bold $-$ ) is multiset.

$$\begin{array}{l}v-v^{\prime }=\left(\bigcup _{\underset{\begin{array}{l}n\cdot a\in v\\ n^{\prime }\cdot a\in v^{\prime }\\ n>n^{\prime }\end{array}}{a\in \left\{a_1,\dots ,a_m\right\}\cap \left\{a_1^{\prime },\dots ,a_{m^{\prime }}^{\prime }\right\}}}\left\{\left(n-n^{\prime }\right)\cdot a\right\}\right)\cup \\ \cup \left(\bigcup _{\underset{n\cdot a\in v}{a\in \left\{a_1,\dots ,a_m\right\}-\left\{a_1^{\prime },\dots ,a_{m^{\prime }}^{\prime }\right\}}}\left\{n\cdot a\right\}\right).\end{array}$$ E33

At last, result of $v$ multiset multiplication by integer number n (recorded as $v\mathbf{\ast }n$ ) is multiset.

$$v\mathbf{\ast }n=\left\{\left(n\times n_1\right)\cdot a_1,\dots ,\left(n\times n_m\right)\cdot a_m\right\}$$ E34

(here integers’ usual multiplication is recorded as $\times$ )

There are also two basic relations on multisets: inclusion ( $\mathbf{\subseteq }$ ) and strict inclusion ( $\mathbf{\subset }$ ).

Multiset v is included to multiset $v^{\prime }$ , that is, $v\mathbf{\subseteq }{v}^{\prime }$ , if

$$\left(\forall n\cdot a\in v\right)\left[\left(\left(\exists n^{\prime }\cdot a\in v^{\prime }\right)n\le n^{\prime }\right)\right],$$ E35

and multiset v is strictly included to multiset $v^{\prime }$ , that is, $v\mathbf{\subset }{v}^{\prime }$ , if $v\mathbf{\subseteq }{v}^{\prime }\&v\mathbf{\ne }{v}^{\prime }.$

Example 1. Let $v_1=\left\{3\bullet \mathit{\text{analyst}},2\bullet \mathit{\text{assistant}}\right\},v_2=\left\{4\bullet \mathit{\text{assistant}},1\bullet \mathit{\text{director}}\right\}$ , then

$$\begin{array}{l}{v}_1\cup v_2=\left\{3\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}},1\cdot \mathit{\text{director}}\right\},\\ v_1\cap v_2=\left\{2\cdot \mathit{\text{assistant}}\right\},\\ v_1\mathbf{+}{v}_2=\left\{3\cdot \mathit{\text{analyst}},6\cdot \mathit{\text{assistant}},1\cdot \mathit{\text{director}}\right\},\\ v_2-v_1=\left\{2\cdot \mathit{\text{assistant}}\right\},\\ v_1\mathbf{\ast }2=\left\{6\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}}\right\},\\ \left\{1\cdot \mathit{\text{analyst}},2\cdot \mathit{\text{assistant}}\right\}\mathbf{\subset }{v}_1,\\ \left\{4\cdot \mathit{\text{assistant}},1\cdot \mathit{\text{director}}\right\}\mathbf{\subseteq }{v}_2.∎\end{array}$$

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:

$$\mathit{n\rho a},$$ E36

$$\mathit{a\rho n},$$ E37

$$\mathit{a\rho }{a}^{\prime },$$ E38

where $a$ and $a^{\prime }$ are the objects, n is the integer number, and $\rho \in \left\{<,=,\le \right\}$ . Chain boundary condition (CBC) is constructed from elementary by writing them sequentially:

$$e_1{\rho }_1{e}_2{\rho }_2\dots e_i{\rho }_i{e}_{i+1}\dots e_m{\rho }_m{e}_{m+1},$$ E39

where $e_1,\dots ,e_{m+1}$ are the objects or nonnegative integers, while ${\rho }_1,\dots ,{\rho }_m$ are the symbols of relations ( $<,=,\le$ ).

EBC semantics is following. Let V be set of multisets, and $v\in V$ . Multiset v satisfies EBC $\overline{n}\mathit{\rho a}$ , if $n\cdot a\in V$ , and $\overline{n}\mathit{\rho n}$ is true. Similarly, v satisfies EBC $\mathit{a\rho }\overline{n}$ , if $\overline{n}\mathit{\rho n}$ is also true. At last, v satisfies EBC ${\mathit{a\rho a}}^{\text{'}}$ , if $n\cdot a\in v$ , $n^{\prime }\cdot a^{\prime }\in v$ , and ${\mathit{n\rho n}}^{\text{'}}$ is true. There is one addition to all listed definitions, concerning particular case, when $n\cdot a\notin v\left(n^{\text{'}}\cdot a\notin v\right)$ , which is equivalent to $n=0\left(n^{\text{'}}=0\right)$ .

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

$$e_1{\rho }_1{e}_2,e_2{\rho }_2{e}_3,\dots ,e_i{\rho }_i{e}_{i+1},\dots ,e_m{\rho }_m{e}_{m+1},$$ E40

and $v\in V$ is considered satisfying CBC (39), if it satisfies all EBC having place in Eq. (40).

Result of application of boundary condition b to SMS V is recorded as $V\downarrow b$ .

Example 2. Let $V=\left\{v_1,v_2\right\},$ where $v_1=\left\{5\cdot \mathit{\text{analyst}},3\cdot \mathit{\text{assistant}},1\cdot \mathit{\text{director}}\right\},v_2=\left\{2\cdot \mathit{\text{assistant}},4\cdot \mathit{\text{director}},3\cdot \mathit{\text{employee}}\right\},$ and boundary conditions are $2\le \mathit{\text{analyst}}\le 4,\mathit{\text{assistant}}<\mathit{\text{employee}},1\le \mathit{\text{director}}\le \mathit{\text{assistant}}\le 3,$ $\text{and}\mathit{\text{analyst}}=\mathit{\text{assistant}}<5.$ Table 1 contains result of application of listed boundary conditions to V. $∎$

$\mathit{\text{condition}}$	$V\downarrow \mathit{\text{condition}}$
$2\le \mathit{\text{analyst}}\le 4$	$\left\{v_2\right\}$
$\mathit{\text{assistant}}<\mathit{\text{employee}}$	$\left\{v_2\right\}$
$1\le \mathit{\text{director}}\le \mathit{\text{assistant}}\le 3$	$\left\{v_1\right\}$
$\mathit{\text{analyst}}=\mathit{\text{assistant}}<5$	$\left\{\varnothing \right\}$

Table 1.

Results of application of boundary conditions.

Optimizing condition has form a = opt, where a is the object, and $\mathit{opt}\in \left\{\text{min},\text{max}\right\}$ . Semantics of this construction is following. Multiset $v\in V$ satisfies condition $a=\text{min}$ , if for every $v^{\prime }\in V$ , such that $v\ne v^{\prime }$ , multiplicity n in multiobject $n\cdot a\in v$ is not greater, than multiplicity $n^{\prime }$ in multiobject $n^{\prime }\cdot a\in v^{\prime }$ , that is, $n\le n^{\prime }$ . Similarly, $v\in V$ satisfies condition $a=\text{max}$ , if for every $v^{\prime }\in V$ , such that $v\ne v^{\prime }$ , multiplicity n in multiobject $n\cdot a\in v$ is not less, than multiplicity $n^{\prime }$ in multiobject $n^{\prime }\cdot a\in v^{\prime }$ , that is, $n\ge n^{\prime }$ . If $a\notin v\left(a^{\prime }\notin v\right)$ , we consider $n\cdot a\in v\left(n^{\prime }\cdot a\in v\right)$ , where $n=0\left(n^{\prime }=0\right)$ .

Filter is join of boundary $F_{\le }$ and optimizing $F_{\mathit{opt}}$ subfilters:

$$F=F_{\le }\cup F_{\mathit{opt}},$$ E41

where $F_{\le }$ is set of boundary conditions, and $F_{\mathit{opt}}$ is set of optimizing conditions. Result of filtration of set of multisets $V$ by filter $F$ is denoted as $V\downarrow F$ and is defined by expression

$$V\downarrow F=\left(V\downarrow F_{\le }\right)\downarrow F_{\mathit{opt}}$$ E42

where

$$F_{\le }=\left\{c_1,\dots ,c_k\right\},$$ E43

$$F_{\mathit{opt}}=\left\{{\mathit{opt}}_1,\dots ,{\mathrm{opt}}_l\right\},$$ E44

$$V\downarrow F_{\le }=\bigcap _{i=1}^k\left(V\downarrow c_i\right)=V^{\prime },$$ E45

$$V^{\prime }\downarrow F_{\mathit{opt}}=\bigcap _{j=1}^l\left(V^{\prime }\downarrow {\mathit{opt}}_j\right),$$ E46

and $c_1,\dots ,c_k$ are EBC. As seen, set $V$ is filtered by boundary conditions, so there are selected multisets, satisfying all of these conditions, and intermediate result $V^{\prime }$ is then filtered by optimizing conditions, so, that multisets, satisfying all of them, are included to the final result.

Example 3. Consider set $V=\left\{v_1,v_2,v_3,v_4\right\}$ , where

$$\begin{array}{l}{v}_1=\left\{3\cdot \mathit{\text{analyst}},2\cdot \mathit{\text{assistant}},2\cdot \mathit{\text{employee}}\right\},\\ v_2=\left\{6\cdot \mathit{\text{assistant}},2\cdot \mathit{\text{director}}\right\},\\ v_3=\left\{1\cdot \mathit{\text{analyst}},3\cdot \mathit{\text{assistant}},5\cdot \mathit{\text{director}},2\cdot \mathit{\text{employee}}\right\},\\ v_4=\left\{1\cdot \mathit{\text{analyst}},2\cdot \mathit{\text{assistant}},2\cdot \mathit{\text{employee}}\right\}.\end{array}$$

Let $F=\left\{1\le \mathit{\text{analyst}}\le 3,2\le \mathit{\text{director}}\le \mathit{\text{employee}},\mathit{\text{analyst}}=\text{min},\mathit{\text{assistant}}=\text{max}\right\}.$ Then, according to Eqs. (41)–(46),

$$V\downarrow F=\left(V\downarrow F_{\le }\right)\downarrow F_{\mathit{opt}},$$

where

$$\begin{array}{l}{F}_{\le }=\left\{1\le \mathit{\text{analyst}}\le 3,2\le \mathit{\text{director}}\le \mathit{\text{employee}}\right\},\\ F_{\mathit{opt}}=\left\{\mathit{\text{assistant}}=\text{min},\mathit{\text{employee}}=\text{max}\right\}.\end{array}$$

Filtration is performed as follows:

$$\begin{array}{l}V\downarrow \left\{1\le \mathit{\text{analyst}}\le 3\right\}=\left\{v_1,v_3,v_4\right\},\\ V\downarrow \left\{2\le \mathit{\text{director}}\le 4\right\}=\left\{v_1,v_2,v_4\right\},\\ V\downarrow F_{\le }=\left\{v_1,v_4\right\},\\ \left\{v_1,v_4\right\}\downarrow \left\{\mathit{\text{assistant}}=\text{min}\right\}=\left\{v_1\right\},\\ \left\{v_1,v_4\right\}\downarrow \left\{\mathit{\text{employee}}=\text{max}\right\}=\left\{v_1,v_4\right\},\\ V\downarrow F=\left\{v_1\right\}\cap \left\{v_1,v_4\right\}=\left\{v_1\right\}.∎\end{array}$$

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.

$$S=⟨v_0,R⟩,$$ E47

where $v_0$ is a multiset called kernel, while 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:

$$v\to v^{\prime },$$ E48

where $v$ (left part of the rule) and $v^{\prime }$ (right part of the rule) are multisets, and $v\ne \left\{\varnothing \right\}.$ Semantics of rule is as follows. Let $\overline{v}$ be multiset; with that we shall speak, that rule (48) is applicable to $\overline{v}$ , if $v\mathbf{\subseteq }\overline{v}$ , and result of its application is a multiset.

$${\overline{v}}^{\prime }=\overline{v}\mathbf{-}v\mathbf{+}{v}^{\prime }.$$ E49

Speaking informally, if $\overline{v}$ includes $v$ , then the last is replaced by $v^{\prime }$ . Application of rule $r\in R$ to multiset $\overline{v}$ is denoted as ${\displaystyle \overline{v}}{\displaystyle \stackrel{r}{\Rightarrow }}\overline{v^{\prime }}$ , and any sequence ${\displaystyle \overline{v}}{\displaystyle \stackrel{r}{\Rightarrow }}\dots {\displaystyle \stackrel{r^{\prime }}{\Rightarrow }}\overline{v^{\prime }}$ is called generation chain.

Set of multisets, defined by MGs $S=⟨v_0,R⟩$ , is denoted as $V_S$ . Iterative representation of MG semantics, that is, SMS $V_S$ generation by application of MG S, is the following:

$$V_{\left(0\right)}=\left\{v_0\right\},$$ E50

$$V_{\left(i+1\right)}=V_{\left(i\right)}\cup \left(\bigcup _{\overline{v}\in V_{\left(i\right)}}\bigcup _{r\in R}\pi \left(\overline{v},r\right)\right),$$ E51

$$V_S=V_{\left(\infty \right)},$$ E52

where

$$\pi \left(\overline{v},v\to v^{\prime }\right)=\left\{\begin{array}{l}\left\{\overline{v}\mathbf{-}v\mathbf{+}{v}^{\prime }\right\},\mathit{\text{if}}v\mathbf{\subseteq }\overline{v},\\ \left\{\varnothing \right\}\mathit{\text{otherwise}}.\end{array}\right.$$ E53

As seen, function (53) implements application of rule $v\to v^{\prime }$ to multiset $\overline{v}$ as described higher. As a result of i + 1-th step of generation, new SMS is formed by application of all rules $r\in R$ to all multisets $\overline{v}\in V_{\left(i\right)}$ , and it is joined to SMS $V_{\left(i\right)}$ . If multiset $\overline{v^{\prime }}$ is generated from multiset $\overline{v}$ by some sequence of such steps, it is denoted as ${\displaystyle \overline{v}}{\displaystyle \stackrel{\ast }{\Rightarrow }}{\displaystyle \overline{v^{\prime }}}$ .

$V_S$ is fixed point of the described process, that is, $V_S=V_{\left(i\right)}$ , where $i\to \infty$ . If for some finite i $V_{\left(i\right)}=V_{\left(i+1\right)}$ , then $V_S=V_{\left(i\right)}$ , and $V_S$ is finite. In the introduced notation,

$$V_S=\left\{v|v_0{\displaystyle \stackrel{\ast }{\Rightarrow }}v\right\}.$$ E54

$V_S$ includes subset ${\overline{V}}_s\subseteq V_s$ of the so-called terminal multisets (TMS) $v\in {\overline{V}}_s$ such that $\pi \left(v,r\right)=\left\{\varnothing \right\}$ for all $r\in R$ , that is, no one multiset may be generated from terminal multiset. Set ${\overline{V}}_S$ is called final; final set consists of terminal multisets only.

Example 4. Let $S=⟨v_0,R⟩$ , where $v_0=\left\{3\cdot \mathit{eur},4\cdot \mathit{usd}\right\}$ ,

$R=\left\{r_1,r_2\right\}$ , where

$r_1$ is $\left\{2\cdot \mathit{eur},1\cdot \mathit{usd}\right\}\to \left\{1\cdot \mathit{eur},1\cdot \mathit{gbp}\right\}$ ,

$r_2$ is $\left\{1\cdot \mathit{eur},2\cdot \mathit{usd}\right\}\to \left\{1\cdot \mathit{eur},2\cdot \mathit{gbp}\right\}$ .

As seen,

$$v_0=\left\{3\cdot \mathit{eur},4\cdot \mathit{usd}\right\}\stackrel{r_1}{\Rightarrow }\left\{2\cdot \mathit{eur},3\cdot \mathit{usd},1\cdot \mathit{gbp}\right\}\stackrel{r_1}{\Rightarrow }\left\{1\cdot \mathit{eur},2\cdot \mathit{usd},2\cdot \mathit{gbp}\right\}\stackrel{r_2}{\Rightarrow }\left\{1\cdot \mathit{usd},4\cdot \mathit{gbp}\right\},$$

$$\left\{2\cdot \mathit{eur},3\cdot \mathit{usd},1\cdot \mathit{gbp}\right\}\stackrel{r_2}{\Rightarrow }\left\{1\cdot a_1,2\cdot \mathit{usd},3\cdot \mathit{gbp}\right\}\stackrel{r_2}{\Rightarrow }\left\{1\cdot \mathit{usd},5\cdot \mathit{gbp}\right\},$$

$$\left\{3\cdot \mathit{eur},4\cdot \mathit{usd}\right\}\stackrel{r_2}{\Rightarrow }\left\{2\cdot \mathit{eur},3\cdot \mathit{usd},2\cdot \mathit{gbp}\right\}\stackrel{r_1}{\Rightarrow }\left\{1\cdot \mathit{eur},2\cdot \mathit{usd},3\cdot \mathit{gbp}\right\}\stackrel{r_2}{\Rightarrow }\left\{1\cdot \mathit{usd},5\cdot \mathit{gbp}\right\},$$

$$\left\{2\cdot \mathit{eur},3\cdot \mathit{usd},2\cdot \mathit{gbp}\right\}\stackrel{r_2}{\Rightarrow }\left\{1\cdot \mathit{eur},2\cdot \mathit{usd},4\cdot \mathit{gbp}\right\}\stackrel{r_2}{\Rightarrow }\left\{1\cdot \mathit{usd},6\cdot \mathit{gbp}\right\}$$

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

$${\overline{V}}_s=\left\{\left\{1\cdot \mathit{eur},4\cdot \mathit{gbp}\right\},\left\{1\cdot \mathit{usd},5\cdot \mathit{gbp}\right\},\left\{1\cdot \mathit{usd},6\cdot \mathit{gbp}\right\}\right\}∎.$$

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 $\left\{1\cdot a\right\}$ , while in the first, there are no any limitations on both parts of rules, excluding, that left part must be nonempty multiset.

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

$$\left\{1\cdot a\right\}\to \left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\}$$ E55

they are written as:

$$a\to n_1\cdot a_1,\dots ,n_m\cdot a_m.$$ E56

Construction (56) is called unitary rule (UR), object a—its head, and unordered sequence (list) $n_1\cdot a_1,\dots ,n_m\cdot a_m$ —its body.

Let us consider UMG formal definition and illustrating example. Unitary multigrammar is couple $S=⟨a_0,R⟩$ , where 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 $V_S$ , where $S=⟨a_0,R⟩,$ is following:

$$V_{\left(0\right)}=\left\{1\cdot a_0\right\},$$ E57

$$V_{\left(i+1\right)}=V_{\left(i\right)}\cup \bigcup _{\overline{v}\in V_{\left(i\right)}}\bigcup _{r\in R}\left\{\overline{\pi }\left(\overline{v},r\right)\right\},$$ E58

$$V_S=V_{\left(\infty \right)},$$ E59

$${\overline{V}}_S=\left\{\overline{v}|\overline{v}\in V_S\&\beta \left(\overline{v}\right)\subseteq {\overline{A}}_s\right\},$$ E60

where

$$\overline{\pi }\left(\overline{v},⟨a\to n_1\cdot a_1,\dots ,n_m\cdot a_m⟩\right)=\left\{\begin{array}{l}\overline{v}\mathbf{-}\left\{n\cdot a\right\}\mathbf{+}n\ast \left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\},\mathit{\text{if}}n\cdot a\in \overline{v},\\ \left\{\varnothing \right\}\mathit{\text{otherwise}}.\end{array}\right.$$ E61

Here, ${\overline{A}}_s$ is set of the so-called terminal objects, such that $a\in {\overline{A}}_s$ , if and only if R does not include URs, which head is a (i.e., a has place only in the UR bodies). ${\overline{A}}_s$ is subset of set $A_s$ of all objects, having places in scheme 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 $a\to n_1\cdot a_1,\cdots ,n_m\cdot a_m$ is written in the angle brackets for unambiguity.

As seen, Eq. (59) defines $V_S$ —set of all multisets, generated by UMG S,—while Eq. (60) by condition $\beta \left(\overline{v}\right)\subseteq {\overline{A}}_s$ provides selection of ${\overline{V}}_S$ —set of terminal multisets (STMS)—from $V_S$ .

Example 5. Consider unitary multigrammar $S=⟨\mathit{\text{company}},R⟩$ , where R includes following unitary rules:

$$\begin{array}{l}\mathit{\text{company}}\to 3\cdot \mathit{\text{group}},2\cdot \mathit{\text{analyst}},\\ \mathit{\text{company}}\to 3\cdot \mathit{\text{analyst}},\\ \mathit{\text{group}}\to 1\cdot \mathit{\text{analyst}},\\ \mathit{\text{group}}\to 2\cdot \mathit{\text{analyst}}.\end{array}$$

According to Eqs. (57)–(61),

$$\begin{array}{l}{V}_S=\left\{\left\{1\cdot \mathit{\text{company}}\right\},\left\{3\cdot \mathit{\text{group}},2\cdot \mathit{\text{analyst}}\right\},\left\{3\cdot \mathit{\text{analyst}}\right\},\left\{5\cdot \mathit{\text{analyst}}\right\},\left\{8\cdot \mathit{\text{analyst}}\right\}\right\},\\ {\overline{V}}_S=\left\{\left\{3\cdot \mathit{\text{analyst}}\right\},\left\{5\cdot \mathit{\text{analyst}}\right\},\left\{8\cdot \mathit{\text{analyst}}\right\}\right\}.∎\end{array}$$

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 $S=⟨a_0,R,F⟩$ , where $a_0$ , R, and F have the same sense, as above, and set of terminal multisets, generated by S, is defined as follows:

$${\overline{V}}_S={\overline{V}}_{⟨a_0,R⟩}\downarrow F,$$ E62

that is, set of terminal multisets, generated by S, is result of filtering STMS, generated by UMGs $⟨a_0,R⟩$ , by filter F.

Example 6. Let $S=⟨\mathit{\text{company}},R,F⟩$ , where R is as in Example 5, while $F=\left\{\mathit{\text{analyst}}>3,\mathit{\text{analyst}}=\text{min}\right\}$ . Then, according to Eqs. (57)–(62),

$$\begin{array}{l}{\overline{V}}_S=\left(\left\{\left\{3\cdot \mathit{\text{analyst}}\right\},\left\{5\cdot a_2\right\}\mathit{\text{analyst}},\left\{8\cdot \mathit{\text{analyst}}\right\}\right\}\downarrow \left\{\mathit{\text{analyst}}>3\right\}\right)\downarrow \left\{\mathit{\text{analyst}}=\text{min}\right\}\\ =\left(\left\{\left\{5\cdot \mathit{\text{analyst}}\right\},\left\{8\cdot \mathit{\text{analyst}}\right\}\right\}\right)\downarrow \left\{\mathit{\text{analyst}}=\text{min}\right\}=\left\{\left\{5\cdot \mathit{\text{analyst}}\right\}\right\}.∎\end{array}$$

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 $⟨a_0,R,F⟩$ , where $a_0$ is the title object, and 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:

$$a\to {\mu }_1\cdot a_1,\dots ,{\mu }_m\cdot a_m,$$ E63

where ${\mu }_i$ is the positive integer number, as in UMGs/FUMGs, or variable $\gamma \in \mathrm{\Gamma }$ , where $\mathrm{\Gamma }$ is the universum of variables. When ${\mu }_i$ is ${\gamma }_i\in \mathrm{\Gamma }$ , then it is called multiplicity-variable (MV). As seen, unitary rule is the simplest particular case of unitary metarule with all multiplicities ${\mu }_1,\dots ,{\mu }_m$ being constants. As in URs, object a in Eq. (55) is called head, while ${\mu }_1\cdot a_1,\dots ,{\mu }_m\cdot a_m$ —body of metarule.

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

$$n\le a\le n^{\prime },$$ E64

$$a=\mathit{opt},$$ E65

$$n\le \gamma \le n^{\prime },$$ E66

where $\mathit{opt}\in \left\{\text{max},\text{min}\right\}$ . As seen, boundary condition (64) and optimizing condition (65) are the same, as in FUMG filters, while boundary condition (65), called variable declaration, defines set of values (domain) of variable $\gamma$ and is denoted lower as $N\left(\gamma \right)$ . If F includes subfilter $F_{\mathrm{\Gamma }}=\left\{n_1\le {\gamma }_1\le n_1^{\prime },\dots ,n_l\le {\gamma }_l\le n_l^{\prime }\right\}$ , containing boundary conditions of form (66), then every combination of variable values ${\overline{n}}_1\in N\left({\gamma }_1\right),\dots ,{\overline{n}}_l\in N\left({\gamma }_l\right)$ provides creation of one unitary multigrammar by substitution of ${\overline{n}}_1,\dots ,{\overline{n}}_l$ to all unitary metarules, having places in scheme R, instead of multiplicities-variables being in their bodies; unitary rules, already having place in R, are transferred to new scheme, denoted $R◦⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩$ , without any transformations. Every such UMGs generates set of terminal multisets, after what all these STMS are joined, and resulting set is filtered by filter $F=F-F_{\mathrm{\Gamma }}$ , containing all “FUMG-like” conditions (From the described, it is obvious nature of “multimetagrammar” notion—in mathematical logic, or “metamathematics,” “metalanguage” is language, used for description of another language, so “multimetagrammar” is “unitary-like” multigrammar, used for description of other unitary multigrammars by means of unitary metarules, variables-multiplicities, and boundary conditions, defining their domains.). As may be seen from this informal description, UMMGs are simple unified tool for compact representation of sets of FUMGs (for practically valuable problems, containing very large numbers of elements—millions and greater).

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,

$$N\left(m\right)=\left\{1,2,3,4,5\right\},$$ E67

$$N\left(n\right)=\left\{1,2,3\right\},$$ E68

$$N\left(l\right)=\left\{1,2,3,4,5,6\right\},$$ E69

so, this one UMMG, consisting of 15 lines, replaces $5\times 3\times 5=75$ filtering unitary multigrammars, each scheme consisting of 10 lines.

Let us now give strict definition of unitary multimetagrammar notion. UMMG $S=⟨a_0,R,F⟩$ defines set of terminal multisets ${\overline{V}}_S$ in such a way:

$${\overline{V}}_S=\left(\bigcup _{{\displaystyle \overline{S}}\in S^{\ast }}{{\displaystyle \overline{V}}}_{{\displaystyle \overline{S}}}\right)\downarrow \mathrm{F},$$ E70

$$S^{\ast }=\bigcup _{{\gamma }_1\in n_1}^{n_1^{\prime }}\dots \bigcup _{{\gamma }_l\in n_l}^{n_l^{\prime }}\left\{⟨a_0,R◦⟨{\gamma }_1,\dots ,{\gamma }_l⟩⟩\right\},$$ E71

$$R◦⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩=\left\{r◦⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩|r\in R\right\},$$ E72

$$\mathrm{F}=F-F_{\mathrm{\Gamma }},$$ E73

$$F_{\mathrm{\Gamma }}=\bigcup _{i=1}^l\left\{n_i\le {\gamma }_i\le n_i^{\prime }\right\},$$ E74

and, at last, if r is $a\leftarrow {\mu }_1\cdot a_1,\dots ,{\mu }_m\cdot a_m,$ then $r◦⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩$ is unitary rule.

$$a\leftarrow \left({\mu }_1◦⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩\right)\cdot a_1,\dots ,\left({\mu }_m◦⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩\right)\cdot a_m,$$ E75

where

$${\mu }_i◦⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩=\left\{\begin{array}{l}{\mu }_i,\text{if}{\mu }_i\in \mathit{N},\\ {\overline{n}}_j,\text{if}{\mu }_i\text{is}{\gamma }_j\in \mathrm{\Gamma }.\end{array}\right.$$ E76

As seen, according to Eqs. (75) and (76), all multiplicities-variables of unitary metarule $a\leftarrow {\mu }_1\cdot a_1,\dots ,{\mu }_m\cdot a_m$ are replaced by their corresponding values from the tuple $⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩$ , while all multiplicities-constants (elements of positive integer numbers set N) remain unchanged. Evidently, if all ${\mu }_1,\dots ,{\mu }_m$ are constants, that is, if unitary metarule is UR, it remains unchanged.

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 $\gamma$ in different unitary metarules (and, of course, in one and the same unitary metarule), they all are substituted by one and the same value from the applied sequence $⟨{\overline{n}}_1,\dots ,{\overline{n}}_l⟩$ .

Example 7. Let us consider UMMG $S=<\mathit{\text{company}},R,F>$ , where scheme R contains following three unitary metarules:

$$\begin{array}{l}\mathit{\text{company}}\to 2\cdot \mathit{\text{group}},{\gamma }_1\cdot \mathit{\text{analyst}},\\ \mathit{\text{group}}\to 3\cdot \mathit{\text{analyst}},{\gamma }_2\cdot \mathit{\text{assistant}},\\ \mathit{\text{group}}\to {\gamma }_1\cdot \mathit{\text{analyst}},{\gamma }_2\cdot \mathit{\text{assistant}},\end{array}$$

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

$$\begin{array}{l}2\le \mathit{\text{analyst}}\le 6,\\ \mathit{\text{assistant}}=\text{min},\\ 0\le {\gamma }_1\le 1,\\ 2\le {\gamma }_2\le 3.\end{array}$$

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

$$\begin{array}{l}{S}_{0,2}=<\mathit{\text{company}},R◦<0,2>>,\\ S_{0,3}=<\mathit{\text{company}},R◦<0,3>>,\\ S_{1,2}=<\mathit{\text{company}},R◦<1,2>>,\\ S_{1,3}=<\mathit{\text{company}},R◦<1,3>>,\end{array}$$

where

$$\begin{array}{l}R◦<0,2>=\{<\mathit{\text{company}}\to 2\cdot \mathit{\text{group}}>,\\ <\mathit{\text{group}}\to 3\cdot \mathit{\text{analyst}},2\cdot \mathit{\text{assistant}}>,<{\mathit{\text{group}}}_1\to 2\cdot \mathit{\text{assistant}}>\},\\ R◦<0,3>=\{<\mathit{\text{company}}\to 2\cdot \mathit{\text{group}}>,\\ <\mathit{\text{group}}\to 3\cdot \mathit{\text{analyst}},3\cdot \mathit{\text{assistant}}>,<\mathit{\text{group}}\to 3\cdot \mathit{\text{assistant}}>\},\\ R◦<1,2>=\{<\mathit{\text{company}}\to 2\cdot \mathit{\text{group}},1\cdot \mathit{\text{analyst}}>,\\ <\mathit{\text{group}}\to 3\cdot \mathit{\text{analyst}},2\cdot \mathit{\text{assistant}}>,<\mathit{\text{group}}\to 1\cdot \mathit{\text{analyst}},2\cdot \mathit{\text{assistant}}>\},\\ R◦<1,3>=\{<\mathit{\text{company}}\to 2\cdot \mathit{\text{group}},1\cdot \mathit{\text{analyst}}>,\\ <\mathit{\text{group}}\to 3\cdot \mathit{\text{analyst}},3\cdot \mathit{\text{assistant}}>,<\mathit{\text{group}}\to 1\cdot \mathit{\text{analyst}},3\cdot \mathit{\text{assistant}}>\},\end{array}$$

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

$$\begin{array}{l}{\overline{V}}_{S_{0,2}}=\left\{\left\{6\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}}\right\},\left\{4\cdot \mathit{\text{assistant}}\right\}\right\},\\ {\overline{V}}_{S_{0,3}}=\left\{\left\{6\cdot \mathit{\text{analyst}},6\cdot \mathit{\text{assistant}}\right\},\left\{6\cdot \mathit{\text{assistant}}\right\}\right\},\\ {\overline{V}}_{S_{1,2}}=\left\{\left\{7\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}}\right\},\left\{3\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}}\right\}\right\},\\ {\overline{V}}_{S_{1,3}}=\left\{\left\{7\cdot \mathit{\text{analyst}},6\cdot \mathit{\text{assistant}}\right\},\left\{3\cdot \mathit{\text{analyst}},6\cdot \mathit{\text{assistant}}\right\}\right\},\\ {\overline{V}}_S=\left({\overline{V}}_{S_{0,2}}\cup {\overline{V}}_{S_{0,3}}\cup {\overline{V}}_{S_{1,2}}\cup {\overline{V}}_{S_{1,3}}\right)\downarrow \left\{2\le \mathit{\text{analyst}}\le 6\right\})\downarrow \left\{\mathit{\text{assistant}}=\text{min}\right\}\\ =\{\left\{6\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}}\right\},\left\{6\cdot \mathit{\text{analyst}},6\cdot \mathit{\text{assistant}}\right\},\left\{6\cdot \mathit{\text{assistant}}\right\},\\ \left\{3\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}}\right\},\left\{3\cdot \mathit{\text{analyst}},6\cdot \mathit{\text{assistant}}\right\}\}\downarrow \left\{\mathit{\text{assistant}}=\text{min}\right\}\\ =\left\{\left\{6\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}}\right\},\left\{3\cdot \mathit{\text{analyst}},4\cdot \mathit{\text{assistant}}\right\}\right\}.∎\end{array}$$

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:

$$\gamma =\mathit{opt}.$$ E77

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 $\gamma$ , which (value) is minimal (maximal) among all other TMS, generated by $\gamma$ application. As seen, Eq. (77) extends optimality definition from only multiplicities-constants, having places in TMS, to also multiplicities-variables, having places in unitary metarules, applied while TMS generation.

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 ${\overline{\gamma }}_1,\dots ,{\overline{\gamma }}_l$ corresponding variables ${\gamma }_1,\dots ,{\gamma }_l$ , having places in UMMG $S=⟨a_0,R,F⟩$ , i.e., unitary metarules and boundary condition (66). After that, let us add one new unitary metarule:

$$a_0^{\prime }\to 1\cdot a_0,{\gamma }_1\cdot {\overline{\gamma }}_1,\dots ,{\gamma }_k\cdot {\overline{\gamma }}_l$$ E78

to scheme R, thus creating scheme $R^{\prime }$ , which contains Eq. (78) and all elements of R, and substituting all optimizing conditions of the form $\gamma =\mathit{opt}$ by $\overline{\gamma }=\mathit{opt}$ in filter F, thus converting them to the “canonical” form (65)—remember, $\overline{\gamma }$ is object not variable and, more, terminal object, because there is no any UR or UMR with head $\overline{\gamma }$ in R. Obtained filter will be denoted as $F^{\prime }$ .

As seen now, UMMG $S^{\prime }=⟨a_0^{\prime },R^{\prime },F^{\prime }⟩$ generates terminal multisets of the form:

$$\left\{n_{i_1}\cdot a_{i_1},\dots ,n_{i_k}\cdot a_{i_k},{\overline{n}}_1\cdot {\overline{\gamma }}_1,\dots ,{\overline{n}}_l\cdot {\overline{\gamma }}_l\right\},$$ E79

where

$$\left\{n_{i_1}\cdot a_{i_1},\dots ,n_{i_l}\cdot a_{i_l}\right\}\in {\overline{V}}_S,$$ E80

and TMS (79) will be selected to ${\overline{V}}_{S^{\prime }}$ , if and only if TMS (80) satisfies all conditions, entering F and concerning terminal objects $a_{i_1},\dots ,a_{i_k}$ , as well as TMS $\left\{{\overline{n}}_1\cdot {\overline{\gamma }}_1,\dots ,{\overline{n}}_l\cdot {\overline{\gamma }}_l\right\}$ satisfies all optimizing conditions of the form ${\overline{\gamma }}_i=\mathit{opt}\in F^{\prime }$ , corresponding ${\gamma }_i=\mathit{opt}\in F.$ .

It is not difficult to define ${\overline{V}}_S$ by subtracting from all $v^{\prime }\in {\overline{V}}_{S^{\prime }}$ multisets of the form $\left\{{\overline{n}}_1\cdot {\overline{\gamma }}_1,\dots ,{\overline{n}}_l\cdot {\overline{\gamma }}_l\right\}$ , but from the practical point of view, it is more useful to consider not ${\overline{V}}_S$ but ${\overline{V}}_{S^{\prime }}$ as a result of application of unitary multimetagrammar S: it is clear that all $v^{\prime }\in {\overline{V}}_{S^{\prime }}$ contain values ${\overline{n}}_1,\dots ,{\overline{n}}_l$ of variables ${\gamma }_1,\dots ,{\gamma }_l$ as terminal objects ${\overline{\gamma }}_1,\dots ,{\overline{\gamma }}_l$ multiplicities, which computation is often main purpose of the mentioned application.

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 $\gamma =\mathit{opt},$ generating TMS like

$$\left\{100\cdot \mathit{\text{employee}},115000\cdot \mathit{eur},3\cdot m,2\cdot n,5\cdot l\right\}$$ E81

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

So we shall use ${\overline{V}}_{S^{\prime }}$ as a result of $S=⟨a_0,R,F⟩$ unitary multimetagrammar application, even if 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 $\subset$ FUMGs): every UMGs is FUMGs with empty filter. From the other side, FUMGs are strict subclass of unitary multiset metagrammars (UMGs $\subset$ FUMGs): every FUMGs is UMMGs without variable multiplicities and corresponding variable declarations inside filter.

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