Open access peer-reviewed chapter

Unitary Multiset Grammars an Metagrammars Algorithmics and Application

Written By

Igor Sheremet

Submitted: October 12th, 2018 Reviewed: November 26th, 2018 Published: December 27th, 2018

DOI: 10.5772/intechopen.82713

Chapter metrics overview

861 Chapter Downloads

View Full Metrics


The chapter is dedicated to the algorithmics of unitary multiset grammars and metagrammars. Their application to some actual problems from the area of large-scale sociotechnical systems (STS) assessment and optimization is also considered: estimation of capabilities of the producing STS; amounts of resources, necessary to such STS for various orders completion; assessment of STS sustainability/vulnerability to various destructive impacts (natural disasters, technogenic catastrophes, mutual sanctions, etc.); and STS profit maximization, as well as works optimal distribution among non-antagonistic competing STS, operating in the market economy.


  • 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

Unitary multiset grammars (UMG) and multimetagrammars (UMMG) are knowledge representation model, providing convergence of classical operations research and modern knowledge engineering. The main area of UMG/UMMG application is assessment and optimization of large-scale sociotechnical systems (STS). Syntax and semantics of multigrammars are described in the first part of this work, being separate chapter of this book. Section 2 of this chapter contains primary description of UMG/UMMG-improved algorithmics, providing generation of terminal multisets (TMS), reduced by unperspective branches cutoff at the maximal early steps of generation. Such branches do not lead to the TMS, satisfying all conditions, entering filter of UMG/UMMG. Section 3 is dedicated to UMG/UMMG application to some actual problems from the STS assessment area (estimation of producing STS capabilities and resources, necessary to such systems for various orders completion, as well as assessment of STS sustainability and vulnerability to various destructive impacts, such as natural disasters, technogenic catastrophes, mutual sanctions, etc.). In Section 4, optimization problems, related to STS, are considered (their profit maximization and works’ optimal distribution among non-antagonistic competing STS in the market economy). Conclusion contains list of directions of further development of multigrammatical approach.


2. Algorithmics of unitary multigrammars and multimetagrammars

Let us begin from filtering unitary multigrammars (FUMG).

From the computational complexity point of view, definition (58) from the first part of this work may be without loss of generated TMS transformed to

V i + 1 = V i v V i a n 1 a 1 n m a m R n a v { v n a + n { n 1 a 1 n m a m } } E1

where means selection of any one multiobject n a from the multiset v instead of repeating such selection for all multiobjects n a v . This provides essential reduction of the computational complexity of TMS generation [1] and is basic for all algorithms, described lower in this section.

As may be seen, sufficiently valuable part of multisets, generated by FUMG unitary rules (UR) application, may be eliminated after few generation steps, because all the following steps do not lead to TMS, satisfying FUMG filter boundary conditions, or have no opportunity for further optimization over terminal multisets, generated earlier, if concerning optimizing conditions. So essence of general approach, which is described further, is to apply filter to every new generated multiset (not only terminal) and to cut off those multisets, which are not perspective in the aforementioned sense. Thus we apply well known and widely used in operations research “branches and bounds” scheme to TMS generation. Of course, filter application to generated nonterminal multisets cannot be identical to filter application to terminal multisets; that is why some additional considerations are necessary.

Let us take the definition of TMS generation logic (57)–(61) from the first part of the work as a basis and construct rather simple and transparent procedure-function terminal multisets generation (TMSG), providing reduced generation of set of terminal multisets, defined by FUMG.

We shall use the following variables in the TMSG body:

  1. v, which value is current generated multiset.

  2. R, which value is set of unitary rules (FUMG scheme), applied to multisets in order to generate new multisets.

  3. F, which value is FUMG filter used for selection of terminal multisets to the resulting set V.

  4. V, accumulating terminal multisets, satisfying filter F, while generation.

  5. FT, which value is set of triples <a, opt, l>, each corresponding to optimizing condition a = opt F , where a is object, opt max min , and l is current value of object a multiplicity obtained after previous generation steps.

  6. Couples <a, w> and <a, c>, which are representations of unitary rule a n 1 a 1 , , n m a m , where w as well as c is multiset n 1 a 1 n m a m .

In TMSG body, F, FT, and V are global variables, which are available from all subfunction calls while generation is executed. Note F is read-only variable, while V and FT are updated (read-write) variables. All other variables are local and are used in the area of their functions in such a way that every new function call operates its own values of these variables.

TMSG body is the following:

TMSG: procedure ( v , R , F ) returns (V);

             variables F , V , FT global; variables v , R local;

              v ; FT ;

            /* initial values of optimized multiplicities settings */

            do a = opt F ;

            case opt :

                       { min : if k a k F

                                      then FT : a min k ;

                                      else FT : a min MAX ;

                       max : if k a k F

                                      then FT : a max k ;

                                      else FT : a max 0 ;


            end F;

            /*main part: generation function G call */

            call G(v, R);

             /*function G body*/

            G: procedure (v, R);

                 if v is terminal multiset

                    then {call FILTER(v);


            /*v is non-terminal multiset, and following operators provide selection of                  unperspective multisets and redundant generation cut-off */

            do n a v where a is terminal object;

                if k a k F & n > k /* n already exceeds higher bound */

                    then return;

                if a min l FT

                    then if l<n /* current minimized multiplicity of object a is already                           lower than n, which cannot decrease */

                                       then return;

             end v;

             /* branch is perspective, so new multisets are generated */

            select n a v where a is non-terminal object;

            do a w R ; /* all non-terminal object a alternatives */

                 call G v n a + n w , R ;

             end aw;


end G;

FILTER: procedure (v); /* generated TMS v filtration */

variables v, x local;

            do n a v ;

                 if k a k F

                      then if n < k n > k /* n is out of k k */

                                  then return;

                 if a min l FT

                      then if l<n /* n is greater than already stored min value */

                                  then return;

                 if a max l FT

                      then if l>n /* n is less than already stored max value */

                                  then return;

            end na;

            /* correction min/max values by new terminal multiset*/

             x 0 ; /* flag “no values corrected” */

            do a opt l FT

                 do n a v ;

                      if l n /* at least one value corrected */

                          then FT : a opt l a opt n / replacement / x 1 } ;

                      / flag reset /

                 end na;

            end opt;

            if x=0 /* no values corrected */

                 then V : v ; /* one more TMS added to the accumulated set */

                 else V v ; /* replacement of earlier accumulated set */

            end FILTER;

end TMSG

Let us comment on the represented procedure-function TMSG.

As seen, it contains prefix, which provides V and FT variable values initialization. FT value is set of triples, each corresponding to one optimizing condition, entering filter F. If there is boundary condition k a k F , then initial value of object a multiplicity would be k in the case condition is a = min , and k otherwise. Both values correspond to the worst cases. If there is not any boundary condition with the same object a, where a = opt F , then, obviously, the worst case for a = min is MAX (the largest possible multiplicity for the considered problem), while for a = max , it is 0. After prefix execution, there is unique operation, returning result of recursive procedure G call with input values v and R, passed without any changes from TMSG call itself.

Procedure G is core of the described algorithm; it implements the main part of generation and consists of three sections.

First section corresponds to that case, when v is terminal multiset, and all that is necessary here is to apply FUMG filter to v, what is really done by procedure FILTER call with v input data. After this call, processing of TMS v is terminated.

If v is not terminal multiset, it is clear that v contains one or more nonterminal objects, which may be used for generation continuation. The last is performed by the second section of G in such a way that multiset v is checked, where it is perspective in the above sense or it may be eliminated from generation, because all TMS, generated from v, would not satisfy F. For this purpose, all terminal multiobjects are checked by two selection criteria:

  1. If in terminal multiobject n a multiplicity n already exceeds upper bound k of boundary condition k a k F . (it’s obvious that while following generation steps, object a multiplicity would only increase or in the utmost case remain unchangeable).

  2. If mentioned multiplicity is greater than value l already having place in the triple a min l FT (again it’s obvious that the following steps would not decrease this multiplicity, so all TMS generated from V would not satisfy optimizing filter a = min ).

(There may be more sophisticated and efficient criteria for earlier recognition and cutting off unperspective generation branches [2, 3], but chapter volume limits make their description impossible). If one of the checked conditions is not satisfied, further generation from multiset v is terminated by return from G without any operation.

The third section of G corresponds to nonterminal multiset, which was not eliminated, being perspective, so generation is continued by all possible branches, corresponding to unitary rules with the same head, in full accordance with UMG semantics and improvement (1), by G recursive calls with new input data.

Function FILTER with unique input (multiset v ) implements check of all conditions, having place in filter F. This is done by the first do-end loop for all terminal multiobjects, entering v. If one of these checks failed, return from FILTER is performed without any additional actions. If all checks were successful, second section is executed. It begins from the installation of flag variable x to 0 value; that means no min/max values in the accumulating variable FT were replaced (i.e., v has no multiobjects n a with value n more or less over already having place in FT). After that, do-end loop for all FT elements is executed. If multiplicity n of object a in TMS v is not equal to value l in the considered element a opt l FT ; that means n is less (when opt = min ) or greater (when opt = max ) than l, so l must be replaced by n, and flag x must get value 1 (at least one replacement was done). The third section of function FILTER operates according to variable x value. If x = 0 (i.e., all optimized multiplicities in v are equal to already obtained in the previous generation steps), then v is joined to the resulting set V as new element. If x = 1 (i.e., at least one multiplicity was replaced, so v is “better” than earlier created and stored terminal multisets), then previous value of V is replaced by one-element set { v }.

As seen, the described algorithm due to its simplicity may be implemented easily on every available software/hardware environment. Correctness of this algorithm is confirmed by the following statement [2, 3].

Statement. Let S = a 0 R F , and TMSG 1 a 0 R F is result of TMSG call. Then

TMSG 1 a 0 R F = V ¯ S . E2

(Note TMSG operates only elementary boundary conditions aρn , not EBC a , neither CBC. TMSG generalization is not associated with any difficulties).

Let us describe now the main idea of algorithmics of generation sets of TMS, defined by unitary multimetagrammars.

As shown in [2, 3], all multisets, generated by any UMMG, have form

v = C a i 1 a i 1 C a i m a i m , E3

where every C a i j is so-called variables-containing multiplicity (VCM), being polynom of variables-multiplicities, having places in unitary metarules, used while generation of multiset v. In the general case, object a VCM is

C a = n i a + i = 1 N C a n i a γ 1 i l i 1 a γ m i i l i m i a , E4

where N C a is number of monoms, each being product of all occurrences of variables-multiplicities and constants-multiplicities, having places in one generation branch, leading to object a.

If filter F of UMMG contains boundary conditions

k 1 a i 1 k 1 , . k l a i l k l E5

as well as optimizing conditions

a j 1 = opt 1 , . a j t = opt t , E6

they induce l inequalities

k 1 C a i 1 k 1 , . k l C a i l k l , E7

and t goal functions

C a j 1 opt j 1 , . C a j t opt j t . E8

Domain of every variable γ , having place in polynoms C a i 1 , , C a i l , C j 1 , , C j t , is defined by boundary condition

k γ γ k γ F . E9

As seen from (3)(9), set of terminal multisets, generated in the UMMG case, corresponds to set of solutions of multicriterial problem of discrete polynomial programming. There are well-known approaches to such problems’ consideration [4, 5], but their common feature is they provide search of any one of the solutions, not all multi-element solutions set, if it exists. Proposed UMMG TMS generation algorithmics [2, 3] is initially oriented to UMMG semantic precise implementation and combines mixed computation and interval analysis techniques [6, 7, 8, 9] with global optimization based on theory [10, 11, 12, 13]. Aforementioned algorithmics provides multidirectional reduction of redundant generation branches by procedure, similar to TMSG, and extended by splitting of intervals, defined by boundary conditions, which describe variable domains, to subintervals, until the last become points. Every such step is accompanied by the estimation of lower and upper bounds of VCMs, containing variable, which current domain is splitted, so if both bounds of at least one VCM are out of interval, defined by corresponding object multiplicity bounds, having place in UMMG filter, then created interval is eliminated, and generation branch is terminated.

As TMSG, another powerful tool of unperspective branches early recognition and cutoff is comparison of mentioned lower and upper bound estimates with already obtained values of optimized multiplicities. If corresponding optimizing condition is a = min, and current value of object a multiplicity, obtained as a result of previous steps execution, is n, then when lower bound estimate of VCM of a is n ¯ , and already n ¯ > n , so further generation by this branch, which leads only to growth of VCM (or it remains unchangeable in the best case), is senseless, and branch may be terminated. Similarly, if optimizing condition is a = max, and current value of corresponding multiplicity is n, while VCM upper bound estimate is n ¯ < n , then further generation by this branch will not lead to object a multiplicity increase, and branch may be terminated.

VCM generation is based on unified representation of polynoms in (4) form as sets of multisets: C a is represented as

v a = n 0 a γ ¯ 0 n 1 a γ ¯ 0 e 1 1 a γ ¯ 1 1 e 1 m 1 a γ ¯ m 1 1 n k a γ ¯ 0 e k 1 a γ ¯ 1 k e k m k a γ ¯ m k k , E10

where k = N C a , γ ¯ j i are objects, corresponding to variables, while γ ¯ 0 is fictive object, corresponding to constants, having place in polynom. For example, polynom

C a = 5 + 3 γ 1 2 γ 2 4 + γ 2 5 γ 3 E11

is represented by multiset

v a = 5 γ ¯ 0 3 γ ¯ 0 2 γ ¯ 1 4 γ ¯ 3 1 γ ¯ 0 5 γ ¯ 2 1 γ ¯ 3 . E12

This representation is sufficiently flexible, and it is the basis of implementation of mixed computation in the multisets case; the core of this implementation is polynoms multiplication and addition.

More detailed description of algorithmics, providing efficient generation of sets of terminal multisets, defined by unitary multimetagrammars, needs separate survey.

Implementation issues, related with the proposed knowledge representation model, are described in [1, 14].

However, presented formal definitions of syntax, semantics, and algorithmics of UMG/UMMG are, in our opinion, sufficient for consideration of their pragmatics, that is, their application to various practical problems.


3. Assessment of the producing sociotechnical systems

Multigrammatical paradigm and UMG/UMMG toolkit are sufficiently general and simple to formalize and solve a lot of practical problems from various areas of operations research and systems analysis. Techniques, shortly described in Section 2 of the first part of this work, is one of the many possible to apply. Some more examples from hierarchical sociotechnical systems assessment and design concerned reader may find in [2, 3], where one may find also description of multigrammatical emulation of well-known classical problems of optimization theory: shortest path, traveling salesman, maximal flow, maximal pair matching, optimal assignments problems, and transport problem as well as integer linear programming problem. (Note that in [2, 3], there is also analysis of interconnections between multigrammars’ family and known computational models, such as Petri nets, vectors addition, substitution systems, etc.).

Lower in this section, we shall consider problems, associated with the producing (manufacturing) STS, being most complicated for modeling.

Let us introduce the following structural interpretation of unitary rules.

We shall understand UR

a n 1 a 1 , , n m a m E13

as follows: object a consists of n 1 objects a 1 , , n m objects a m .

In turn, technological interpretation of unitary rules is generalization of the structural one and is as follows: production of one object (unit of resource) a requires n 1 objects (units of resource) a 1 , , n m objects (units of resource) a m . One may consider (13) as a black box, representing producing device or manufacturing facility (factory, plant, etc.), containing a lot of such devices, working cooperatively. Set R of such URs represents technological base (TB) of some social group, possessing represented by this set producing (manufacturing) equipment. If R contains l > 1 URs with identical head and different bodies, this means that one and the same object may be produced in l various ways (by l various devices, or by one and the same device, but by various methods, or by l various facilities). Objects, having places in URs, may be manufactured devices, their blocks, spare parts, chips, pieces of connecting cables, various measured resources involved (necessary amounts of electrical energy, liquids, solid materials, etc. “down to ore”), as well as time and money. Manufactured devices may be, in turn, manufacturing (“means of production”) and may be used further in production processes/chains.

Unitary multigrammars provide most natural “top-down” way of formal description of technological base of arbitrary producing STS, as well as deep structure of manufactured objects of any level of structural complexity (obviously, these two entities are interconnected closely). “Additivity” of multigrammatical knowledge bases (KB), being consequence of their “granularity” (due to unitary rules and metarules as knowledge representation atoms), provides creating and updating KB in near real time. Since now we shall use notations “multigrammatical knowledge base” and “scheme of UMG/UMMG” as synonyms.

Example 1. Consider car, consisting of body, engine, transmission, four wheels, and fuel cistern. Car body, in turn, consists of frame, front and back glasses, engine cover, baggage place, and two first and two second doors. Engine includes motor, cooling system, and accumulator. All the said may be represented by the following set of unitary rules in the structural interpretation:

car 1 body , 1 engine , 1 transmission , 4 wheel , 1 fuel cisterm , body 1 frame , 1 front glass , 1 back glass , 1 engine cover , 1 baggage place , 2 first door , 2 back door , engine 1 motor , 1 cooling system , 1 accumulator .

As it is easy to see, all terminal objects may become nonterminal after joining to this set of new URs, detailing them down to undivided spare parts. If to follow technological interpretation, then every UR reflects assembling operation, implemented by corresponding segment of manufacturing facility: one such segment is assembling car of the listed components, another segment - body, etc.

To take into account cost of any operation executed (obviously, it is “added valuein K. Marx terminology), as well as time interval necessary for its execution, it is sufficient to include to UR bodies multiobjects like n e and m t , where e and t are fixed-name objects being cost and time measurement units (e.g., usd and sec). There may be recalculation of both to another unit by including to the KB additional rules, reflecting currencies interrelations and different time scales, for example,

eur 1.15 usd , E14
hour 60 mnt , E15
mnt 60 sec E16

(rational multiplicities’ appearance along with integer ones, considered higher, does not bring any principal transformations and difficulties into MG semantics and algorithmics [2, 3]). Both cost and time may be defined in “compound” units, that is, UR body may contain three multiobjects, 3 hour , 23 min , 15 sec , that after application of URs (14)–(16) will be transformed to one multiobject, 10953 sec .

Considering time intervals description in unitary rules, we must take into account that, unlike cost, time is not fully additive resource, because producing devices may operate in parallel. That’s why time is additive resource only regarding separate device, and typical form of “local time” description is multiobject n t x , where x may be manufacturing device name as well as assembled technical object name, while t is time measurement unit (here angle brackets are used for syntactical unambiguity).

Example 2. Let us consider the following cost and time parameters, implanted to URs from example 1. Let cost of one car assembling is 3000 USD; body, 2000 USD; and engine, 6000 USD; time interval necessary for one car assembling is 28 minutes, body, 21 minutes; and engine, 63 minutes. Then URs from Example 1 may be rewritten in the following way:

car 28 mnt car , 3000 usd , 1 body , 1 engine , 1 transmission , 4 wheel , 1 fuel cisterm , body 21 mnt body , 2000 usd , 1 front glass , 1 back glass , 1 engine cover , 1 baggage place , 2 first door , 2 back door , engine 60 mnt engine , 6000 usd , 1 motor , 1 cooling system , 1 accumulator .

If we have knowledge base, prepared as shown above, then it may be used to estimate resources amounts, necessary to complete any order by means of technological base, defined by R. Order may be represented as multiset

q = m 1 b 1 m k b k , E17

which means customer needs m 1 objects b 1 , , m k objects b k .

Then, as it is easy to see, resources collection, necessary to complete this order, is terminal multiset v ¯ being element of set of TMS V ¯ S q , where

S q = a q R q , E18
R q = R a q m 1 b 1 m k b k E19

(unitary rule, having place in (19), is in angle brackets for unambiguity). If unitary multigrammar S q generates one-element SMS, that is, V ¯ S q = 1 , there is unique variant of aforementioned resources collection. Otherwise, V ¯ S q > 1 , and there are various ways of some objects’ assembling, each consuming its own resources collection.

Example 3. Let q = 3 car . Then R q consists of all URs from Example 2 and unitary rule

order 3 car , E20

that is, order is to assemble three cars. According to (17)(19),

V ¯ S q = 84 mnt car 63 mnt body 180 mnt engine 27000 usd , 3 transmission , 12 wheel , 3 fuel cistern , 3 front glass , 3 back glass , 3 engine cover , 3 baggage place , 6 first door , 6 back door , 3 motor 3 cooling system 3 accumulator .

That means order completion requires spare parts from external suppliers as well as money and time for assembling segments of manufacturing facility in amounts, being multiplicities of corresponding objects, having places in V ¯ S q . There is the only one variant of resources set necessary for order completion.▪

If it is necessary to evaluate (estimate) total cost of order completion, then it is sufficient to join to the KB R unitary rules, defining costs of all necessary spare parts and other external (“outsourced”) resources. These URs may have form a n e , where a is terminal object from R, while e is monetary unit, used for cost calculation. As may be seen, if one would eliminate from URs time-defining multiobjects, then e becomes unique terminal object of the created scheme R , and set of terminal multisets generated by UMG S = a q R q would contain one-element TMS of form n ¯ e , where n ¯ is total cost of order completion, corresponding to one of its variants (as was said higher, there may be more than one such variant).

Example 4. Let us add to the KB from Example 3 the following unitary rules, defining prices of car the outsourced elements:

transmission 100 usd , wheel 50 usd , accumulator 10 usd .

As seen, new UMG provides generation of one-element set

84 mnt car 63 mnt body 180 mnt engine X usd ,

where X is total cost of order completion, that is, three car assembling.

If multiobjects 28 mnt car , 21 mnt body and 60 mnt engine are eliminated from UR set presented in Example 10, then obtained UMG will generate one-element set {{X usd }}.▪

In practice every STS, which is capable to complete input orders and manufacture some output production, possesses usually not only technological base but also resource base (RB). For this reason, assessment of STS capability to orders completion requires comparison of two resources collections—being in system’s ownership and necessary. In multigrammatical paradigm, this problem is solved quite simply.

Let R be technological base, while multiset v ¯ = m ¯ 1 b ¯ 1 m ¯ k b ¯ k is resource base of the system, that is, STS possesses m ¯ 1 objects b ¯ 1 , , m ¯ k objects b ¯ k . As it is easy to see, order q = m 1 b 1 m l b l may be completed by this system, if there exists multiset v V ¯ S q such that

v v ¯ , E21

that is, collection of resources, belonging to the STS, is sufficient for order q completion by one of the implementable ways. In this case order completion is possible. Otherwise, that is, if there is no one multiset v V ¯ satisfying (21), then system is not able to complete q.

Example 5. Let KB from Example 2 be STS technological base, while

v ¯ = 6 transmission , 10 wheel , 2 fuel cistern , 7 front glass , 9 back glass , 180 mnt car , 240 mnt body , 600 mnt engine , 1000000 eur , 500000 usd

is its resource base. As may be seen, this resource base is not sufficient for order q = {3 car} from Example 11 completion, because condition (21) is not satisfied: there are objects, entering all v V ¯ S q , which do not enter v ¯ at all (motor, accumulator, etc.). At the same time multiplicities of some terminal objects are less than it is necessary for order q completion 2 fuel cistern v ¯ while 3 fuel cistern v V ¯ S q .▪

After recognition of system’s inability to complete order q, there may be two questions:

  1. What amount of resources must be acquired by the system to complete the order?

  2. What part of order may be completed, given resources, owned by STS?

The answer to the first question is obvious: if v V ¯ S q , and v is not subset of v ¯ , then additional amount of resources, necessary for order completion, is v ¯ v . Thus variants of necessary resources acquisition are elements of set of terminal multisets

Δ V ¯ S q = v ¯ v v V ¯ S q . E22

The answer to the second question concerned reader may find in [1], where the so-called reverse multigrammars are used for this problem solution.

One more area of useful application of UMG/UMMG is assessment of sociotechnical systems sustainability/vulnerability to various destructive impacts, which was in details considered in [1]. The main result of this work is as follows.

Let R q be scheme, corresponding to technological base of the system and order q in the sense (17)(19); v ¯ is total resource of this system (resource base, joined with multiset representation of technological base, as it was suggested in [1]), and Δ v ¯ is impact, destructing some part of the aforementioned total resource. We shall call STS with technological base R and total resource v ¯ sustainable to impact Δ v ¯ while completing order q, if

v V ¯ S q v v ¯ Δ v ¯ . E23

That is, despite impact there is at least one way of order completion. Otherwise, if there is no one TMS v V ¯ S q , satisfying (23), considered STS is vulnerable to impact Δ v ¯ .


4. Optimization problems

Another important issue to be discussed here is profit optimization in production economy (POPE). We shall consider it not only because of its practical value but also in order to illustrate techniques of UMG/UMMG application to the multigrammatical representation and solution of classical optimization problems.

POPE is formulated as follows [15]. Let there be n products, manufactured by STS, x i is amount of i-th product, and c i is its price. Profit, which producing STS would obtain, is

C = i = 1 m c i x i . E24

To produce one unit of i-th product, the system needs respective resources, namely, a ij units of the j-th resource, where j = 1 , , n , and n is total number of different resources, consumed by the system for production. There are b1, …, bn amount of resources available, and the problem is to maximize profit C under restrictions

i = 1 m a ij x i b j , E25

where j = 1 , , n .

This problem may be represented by unitary multiset metagrammar S = < q , R , F > , which scheme R contains one unitary metarule

q x 1 u 1 , , x m u m , E26

where x 1 , , x m are variables, and m unitary rules

u i ai 1 e 1 , , ai n e n , c i e , E27

where i = 1 , , m , and a ij is nonzero amount of j-th resource, needed for i-th product, while c i is its price. Filter F contains n boundary conditions

e j b j , E28

where j = 1 , , n , as well as one optimizing condition

e = max , E29

along with m variable declarations

0 x i M i , E30

where i = 1 , , m and M i is maximal amount of i-th product, which may be manufactured by the system. As seen, terminal objects e 1 , , e n are measurement units of corresponding resources, while terminal object e is price measurement unit. Nonterminal objects u 1 , , u m represent products, and UMR (26) along with optimizing condition (29) represents order, while n URs (27) represent STS technological base. STS resource base, as it was introduced higher, is represented by boundary conditions (28).

As may be seen, set of POPE solutions is

V S ¯ = v 1 v t , E31


l 1 e 1 l n e n C e p 1 x ¯ 1 p m x ¯ m V S ¯ E32

means that maximal profit is C and it is gotten when STS produces p 1 units of the first product, …, p m units of the m-th product. In general case

V S ¯ > 1 , E33

so there may be t > 1 solutions of the specific POPE.

Example 6. Let POPE is

2 x 1 + 3 x 2 max

under restrictions

3 x 1 + 2 x 2 10
5 x 1 + 3 x 2 18 .

That means STS is producing two products, which prices are 2 and 3, respectively, and there is resource base, containing 10 units of the first resource and 18 units of the second. To produce one unit of the first product, STS needs 3 units of the first resource and 5 units of the second, while producing of one unit of the second product needs 2 units of the first resource and 3 units of the second resource.

According to (26)(30), scheme R of the corresponding UMMG S = < q , R , F > includes UMR

q x 1 u 1 , x 2 u 2 ,

as well as two URs:

u 1 3 e 1 , 5 e 1 , 2 e ,
u 2 2 e 1 , 3 e 2 , 3 e .

Filter F contains two boundary conditions

e 1 10 ,
e 2 18 ,

one optimizing condition

e = max ,

as well as two variables declarations:

0 x 1 10 ,
0 x 2 10 ,

where 10 is maximal amount of any product, which may be produced by STS.

As seen,

V ¯ S = 10 e 1 16 e 2 10 e 2 x ¯ 1 2 x ¯ 2 ,

which means STS would get maximal profit of 10 units, producing 2 units of both products and, spending for that purpose, 10 units of the first resource and 16 units of the second resource.▪

Let us note that classical matrix–vector POPE modeling is limiting set of the considered cases to the simplest two-level structures of the manufactured objects (“object-component”), represented by unitary rules like (27). In practice, all such objects have much more complicated, multilevel heterogeneous hierarchical structure, that is clearly illustrated by the previous Examples 1–3, concerning car manufacturing.

UMMG application provides natural representation of the POPE problem in the most general formulation. Namely, it is sufficient to join to set of URs, describing technological base of the STS, the only UMR like (26). Similarly, to represent resource base of the STS, filter of the created UMMG would contain boundary conditions like (28); it is important that absence of some resource e in the RB must be represented by boundary condition e = 0; otherwise any generated TMS, containing multiobject n · e , where n > 0, may enter one of the solutions, and this contradicts reality. The goal of STS is defined by the optimizing condition like (29), and domains of variables, having place in the aforementioned UMR, are defined by variable declarations like (30). If it is necessary to maximize profit, taking into account expenses for some resources acquisition, it is very convenient to use representation of prices of the acquired resources, as it was illustrated by Example 4, but with negative multiplicities (such techniques are described in [2, 3]), that is, as to URs from Example 4,

transmission 100 usd , wheel 50 usd , accumulator 10 usd .

To cut off generated TMS with nonpositive multiplicities of object e (such TMS correspond to unprofitable variants), it is sufficient to join to UMMG filter one more boundary condition e > 0. However, the use of negative multiplicities leads to some corrections in UMG/UMMG algorithmics, which would be considered separately.

All the said higher in this section is very close to the Leontief model and other “input–output” models of mathematic economy, developed on the matrix–vector algebra basis [16]. As may be seen, transfer to the UMG/UMMG basis makes such modeling much more flexible and closer to the reality. That is why we consider multigrammatical paradigm as very perspective for the development of various issues in the future digital economy [17, 18], first of all, planning and scheduling in the cyberphysical industry, integrated with deeply robotized logistics [19, 20]. However, application of the described here approach to the core areas of digital economy (Industry 4.0) needs separate publications.

Concerning implementation issues, it would be aptly to say that multisets processing is very promising area for application of non-conventional computing paradigms [21, 22].

Now let us spend some place of this section for multiset modeling of competitions and works distribution in the concurrent environment, typical for market economy.

The main tool of the last is the so-called variative unitary multigrammars and multimetagrammars, which schemes include unitary rules (metarules) with the same head and different bodies. UMG/UMMG variativity provides representation of coexistence of various subjects able to complete one and the same order. We assume these subjects are non-antagonistic, that is, they all are ready to execute any part of the total work.

There may be at least three possible approaches to multigrammatical modeling of competitions:

  1. “The winner takes it all.”

  2. Splitting order among various subjects.

  3. “The winner coalition takes it all” (combination of two previous).

Let us consider the first approach.

Let R be set of unitary rules containing, among others, k URs with one and the same head and different bodies:

a n 1 1 a 1 1 , , n m 1 1 a m 1 1 , a n 1 k a 1 k , , n m k k a m k k . E34

where i-th alternative corresponds to i-th subject of considered technological base, able to produce object a, consuming for that purpose n 1 i objects a 1 i , , n m i i objects a m i i . To simplify and unify recognition of variant implemented, let us introduce k terminal objects s 1 , , s k , being names of corresponding subjects, and replace set (34) by

a 1 s 1 , n 1 1 a 1 1 , , n m 1 1 a m 1 1 , a 1 s k , n 1 k a 1 k , , n m k k a m k k . E35

Let q = n a , and R q is set of URs, containing UR

a q n a , E36

k URs (35), and all unitary rules from set R, excluding (35). Consider UMG S q = a q R q . As seen, V ¯ S q is set of terminal multisets, each corresponding to some variant of order q completion. If we establish filter F q to select one and only one element of V ¯ S q , transforming UMG S q to FUMG S q = a q R q F q , this element will be

n s i m 1 i b ¯ 1 i m l i i b ¯ l i i , E37

where multiobject n s i corresponds to n operation cycles of subject s i during order q completion and every multiobject m j i b ¯ j i corresponds to m j i terminal objects b ¯ j i , required for these cycles’ implementation. In this context, filter F q may contain boundary conditions, defining required resources limits, as well as optimizing conditions, defining some of terminal object b ¯ j i multiplicities as minimal (e.g., cost, electrical energy, or fuel consumed) or maximal (e.g., some integral parameters of quality of produced objects or given services). If subject s i becomes the only winner, it takes all order to complete.

Example 7. Let us consider following unitary rules:

car 1 first , 30 mnt car , 2800 usd , 1 accessories set , car 1 second , 40 mnt car , 2700 usd , 1 accessories set , car 1 third , 45 mnt car , 2500 usd , 1 accessories set .

These URs being joined with URs, detailing nonterminal object accessories set from R, describe competition of three car manufacturers (first, second, and third), assembling cars from one and the same accessories but differing by the time spent for this operation and its cost. If we consider FUMG S q = a q R F , where q = 3 car and F = usd = min , then

V ¯ S q = 1 third X usd 135 mnt car ,

which corresponds to the choice of the third manufacturer. If F = usd = min mnt car = min , then

V ¯ S q = ,

because no one of the possible order executors is optimal by time and cost simultaneously.▪

As it is well known from practice, approach, described higher, may be not rational from various points of view, especially, when capabilities of no one of the competitors (subjects s 1 , , s k ) are not sufficient for the whole order completion. In this case, more rational may be the second approach when order is splitted between non-antagonistic (cooperating) competitors in such a way that the total amount of objects produced is distributed among subjects s 1 , , s k . This techniques may be modeled by unitary multimetagrammar S q , which scheme R q includes unitary metarule

a q γ 1 b 1 , , γ k b k , E38

and unitary rules

b 1 1 a , n 1 1 a 1 1 , , n l 1 1 a l 1 1 , b k 1 a , n 1 k a 1 k , , n l k k a l k k , E39

as well as all URs, having place in the scheme, constructed higher by application of the first approach, excluding (34). Filter F q contains boundary condition

a = n , E40

which is directly induced by order q = n a and boundary conditions, defining domains of variables γ 1 , , γ k :

0 γ i n . E41

As seen, terminal multisets, generated by UMMG S = a q R q F q , have form

n a n 1 γ ¯ 1 n k γ ¯ k m 1 i b ¯ 1 i m l i i b ¯ l i i , E42

where, according to (38)(40),

i = 1 k n i = n , E43

and thus values n 1 , , n k are parts of order q = n a , distributed among subjects s 1 , , s k , respectively: s 1 will produce n 1 objects a, s 2 n 2 objects a, up to s k , which will produce n k objects a.

Example 8. Let us transform set R from Example 7 to the following:

order γ 1 first , γ 2 second , γ 3 third , first 1 car , 2800 usd , 2800 usd 1 , 1 accessories set , second 1 car , 2500 usd , 2500 usd 2 , 1 accessories set , third 1 car , 2200 usd , 2200 us d 3 , 1 accessories set .

If order q = 10 car , then F q = car = 10 0 γ 1 10 0 γ 2 10 0 γ 3 10 F q , where F q may contain boundary and optimizing conditions, selecting terminal multisets, for example, F q = usd = min usd 1 2800 usd 2 5000 usd 3 6600 . According to such F q , set of terminal multisets, generated by UMMG S q = a q R q F q , may contain element of the form { 10 car , 25600 usd , 14000 usd 1 , 5000 usd 2 , 6600 usd 3 , 5 γ 1 , 2 γ 2 , 3 γ 3 , } ,

which corresponds to splitting order q in such a way that five cars would be assembled by the first manufacturer, two by the second, and three by the third.▪

Let us underline once more that time is not additive resource in relation to parallel processes; it is additive only regarding one device (manufacturing unit). Consideration of multisets with time-containing multiobjects is separate direction of the multigrammatical approach and needs special tool, which is called temporal multiset grammars (TMG), announced in [1] . This branch concerns problems, addressed by the classical theory of scheduling [23, 24].

The third possible case of competitions (“the winner coalition takes it all”) may be considered by the concerned reader on his (her) own.


5. Conclusion

Presented primary survey of multigrammatical knowledge representation along with brief consideration of its possible applications is, of course, only a background for future development, which most valuable directions may be:

  1. MG/UMG/UMMG extension by features, necessary for “single-time-scale” modeling of manufacturing and logistical processes and their optimal control, that is critically needed for the developed digital economy (Industry 4.0)

  2. Development of algorithmics for local correction of solutions (generated sets of TMS) while UMG/UMMG local correction in the sense [25], which is necessary for the aforementioned control in hard real-time and highly volatile environment

  3. Further development of MG/UMG/UMMG improved algorithmics and its software/hardware implementation in high-parallel general-purpose computing environments

  4. Development of specialized high-parallel computing environments, initially oriented to MG/UMG/UMMG algorithmics implementation

  5. Development of quantum, neural and molecular algorithmics for MG/UMG/UMMG toolkit implementation in corresponding computer environments

  6. MG/UMG/UMMG pragmatics expansion to new problem areas and convergence with other known knowledge/data engineering paradigms (first of all, multiagent systems [15, 26, 27])

Some of the listed directions are already developed by the author and his colleagues; some are waiting their time, being targeted to the creation of unified framework for the intellectual (knowledge-based) digital economy. This way is leading us to the Big Knowledge paradigm being generalization of the Big Data one, which is already everyday reality. The author will be glad, if this paper will be of any interest for some scholars working in the related areas.



The author is grateful to Prof. Fred Roberts for useful discussions and support, and to Prof. Jeffrey Ullman, whose useful remarks on the primary version of this work contributed to its essential upgrade. A significant incentive for the development of the proposed approach was its positive assessment by Prof. Noam Chomsky, which early works on syntactic structures formed a conceptual background of the described mathematical toolkit.


  1. 1. Sheremet I. Multiset analysis of consequences of natural disasters impacts on large-scale industrial systems. Data Science Journal. 17(4):1-17. DOI: 10.5334/dsj-2018-004
  2. 2. Sheremet IA. Recursive Multisets and Their Applications. Moscow: Nauka; 2010. p. 293. (In Russian)
  3. 3. Sheremet IA. Recursive Multisets and Their Applications. Berlin: NG Verlag; 2011. p. 249
  4. 4. Lasdon SL. Optimization Theory for Large Systems. NY: Dover Publications; 2013. p. 560
  5. 5. Hemmecke R, Koppe M, Lee J, Weismantel R. Nonlinear Integer Programming. In: 50 Years of Integer Programming 1958–2008: The Early Years and State-of-the-Art Surveys. NY: Springer-Verlag; 2009. pp. 1-57. DOI: 10.1007/978-3-540-68279-0-15
  6. 6. Ershov AP. On the partial computation principle. Information Processing Letters. 1977;2(2):38-41
  7. 7. Bjorner D, Ershov AP, Jones ND, editors. Partial Evaluation and Mixed Computation. North Holland: Amsterdam; 1988. p. 625
  8. 8. Itkin VE. An algebra of mixed computation. Theoretical Computer Science. 1991;90(1):81-93
  9. 9. Lloyd JW, Shepherdson JC. Partial evaluation in logic programming. Journal of Logic Programing. 1991;11(3–4):217-242. DOI: 10.1016/0743-1066(91)90027–M
  10. 10. Hansen E. Global optimization using interval analysis—The one-dimensional case. Journal of Optimization Theory and Applications. 1979;29:331-334
  11. 11. Hansen E. Global Optimization Using Interval Analysis. NY: Marcel Dekker; 1992. p. 284
  12. 12. Hansen E, Walster GW. Global Optimization Using Interval Analysis. NY: Marcel Dekker; 2004. p. 530
  13. 13. Fiedler M, Nedoma J, Ramik J, Rohn J, Zimmerman K. Linear Optimization Problems with Inexact Data. NY: Springer; 2006. p. 227
  14. 14. Sheremet IA. Augmented Post Systems: The Mathematical Framework for Knowledge and Data Engineering in Network-Centric Environment. Berlin: EANS; 2013. p. 395
  15. 15. Shoham Y, Leyton-Brown K. Multiagent Systems. Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge, UK: Cambridge University Press; 2009. p. 532
  16. 16. Bjerkholt O, Kuzz HD. Introduction: The history of input-output analysis, Leontief’s path and alternative tracks. Economic Systems Research. 2006;18(4):331-333. DOI: 10.1080/09535310601030850
  17. 17. Schwab K. The Fourth Industrial Revolution. What It Means and How to Respond. Foreign Affairs. December 12, 2015. Available from:
  18. 18. Baller S, Dutta S, Lanvin B, editors. The Global Information Technology Report 2016. Innovating in the Digital Economy. Geneve: WEF and INSEAD; 2016. p. 62
  19. 19. Colombo AW, Bangemann T, Karnouskos T, Delsing J, Stluka P, Harrison R, et al. Industrial Cloud-Based Cyber-Physical Systems: The IMC-AESOP Approach. NY: Springer Verlag; 2014. p. 245
  20. 20. Lee J, Bagheri B, Hung-An K. A cyber-physical systems architecture for Industry 4.0-based manufacturing systems. Manufacturing Letters. 2015;3:18-23. DOI: 10.1016/j.mfglet.2014.12.001
  21. 21. Montanaro A. Quantum algorithms: An overview. npj Quantum Information. 2015;2:15023. DOI: 10.1038/npjqi.2015.23
  22. 22. Farhi E, Goldstone J, Gutmann S. A quantum approximate optimization algorithm applied to a bonded occurrence constraint problem. In: Quantum Physics. Report MIT-CTP/4628. NY: Cornell University, 2015. arXiv: 1412.6062
  23. 23. Conway RW, Maxwell WL, Miller LW. Theory of Scheduling. Mineola, NY: Dover Publications; 2003. p. 304
  24. 24. Leung JY-T, editor. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. NY: Chapman & Hall/CRC; 2004. p. 1224
  25. 25. Sheremet IA. Intelligent Software Environments for Computerized Information Processing Systems. Moscow: Nauka; 1994. p. 544. (In Russian)
  26. 26. Wooldridge M. An Introduction to Multi-Agent Systems. Chichester, England: John Wiley & Sons; 2009. p. 460
  27. 27. Salamon T. Design of Agent-Based Models. Repin-Zivolin: Brukner Publishing; 2011. p. 220

Written By

Igor Sheremet

Submitted: October 12th, 2018 Reviewed: November 26th, 2018 Published: December 27th, 2018