Open access peer-reviewed chapter

Unitary Multiset Grammars an Metagrammars Algorithmics and Application

By Igor Sheremet

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

DOI: 10.5772/intechopen.82713

Downloaded: 465


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


where means selection of any one multiobject nafrom the multiset vinstead of repeating such selection for all multiobjects nav. 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 TMSGbody:

  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=optF, where ais object, optmaxmin, and lis current value of object amultiplicity obtained after previous generation steps.

  6. Couples <a, w> and <a, c>, which are representations of unitary rule an1a1,,nmam, where was well as cis multiset n1a1nmam.

In TMSGbody, F, FT, and Vare global variables, which are available from all subfunction calls while generation is executed. Note Fis read-only variable, while Vand FTare 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.

TMSGbody is the following:

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

             variablesF,V,FTglobal; variablesv,Rlocal;


            /* initial values of optimized multiplicities settings */






                       max : ifkakF





            /*main part: generation function Gcall */

            callG(v, R);

             /*function Gbody*/

            G: procedure(v, R);

                 ifvis terminal multiset



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

            donavwhereais terminal object;

                ifkakF&n>k/* nalready exceeds higher bound */

                    then return;


                    then ifl<n /*current minimized multiplicity of object ais already                           lower than n, which cannot decrease */

                                       then return;


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

            selectnavwhereais non-terminal object;

            doawR; /* all non-terminal object aalternatives */





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

variablesv, xlocal;



                      then ifn<kn>k/* nis out of kk*/

                                  then return;


                      then ifl<n/* nis greater than already stored min value */

                                  then return;


                      then ifl>n/* nis less than already stored max value */

                                  then return;


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

            x0;/* flag “no values corrected” */



                      ifln/* at least one value corrected */


                     /flag reset/



            ifx=0 /* no values corrected */

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

                 elseVv;/* replacement of earlier accumulated set */



Let us comment on the represented procedure-function TMSG.

As seen, it contains prefix, which provides Vand FTvariable values initialization. FTvalue is set of triples, each corresponding to one optimizing condition, entering filter F. If there is boundary condition kakF,then initial value of object amultiplicity would be kin the case condition is a=min, and kotherwise. Both values correspond to the worst cases. If there is not any boundary condition with the same object a, where a=optF, then, obviously, the worst case for a=minis 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 Gcall with input values vand R,passed without any changes from TMSGcall itself.

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

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

If vis not terminal multiset, it is clear that vcontains one or more nonterminal objects, which may be used for generation continuation. The last is performed by the second section of Gin such a way that multiset vis 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 namultiplicity nalready exceeds upper bound kof boundary condition kakF. (it’s obvious that while following generation steps, object amultiplicity would only increase or in the utmost case remain unchangeable).

  2. If mentioned multiplicity is greater than value lalready having place in the triple aminlFT(again it’s obvious that the following steps would not decrease this multiplicity, so all TMS generated from Vwould 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 vis terminated by return from Gwithout any operation.

The third section of Gcorresponds 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 Grecursive calls with new input data.

Function FILTERwith unique input (multiset v) implements check of all conditions, having place in filter F. This is done by the first do-endloop for all terminal multiobjects, entering v. If one of these checks failed, return from FILTERis performed without any additional actions. If all checks were successful, second section is executed. It begins from the installation of flag variable xto 0 value; that means no min/max values in the accumulating variable FTwere replaced (i.e., vhas no multiobjects nawith value nmore or less over already having place in FT). After that, do-endloop for all FTelements is executed. If multiplicity nof object ain TMS vis not equal to value lin the considered element aoptlFT; that means nis less (when opt=min) or greater (when opt=max) than l, so lmust be replaced by n, and flag xmust get value 1 (at least one replacement was done). The third section of function FILTERoperates according to variable xvalue. If x = 0 (i.e., all optimized multiplicities in vare equal to already obtained in the previous generation steps), then vis joined to the resulting set Vas new element. If x = 1 (i.e., at least one multiplicity was replaced, so vis “better” than earlier created and stored terminal multisets), then previous value of Vis 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=a0RF, and TMSG1a0RFis result of TMSGcall. Then


(Note TMSGoperates only elementary boundary conditions aρn, not EBC a, neither CBC. TMSGgeneralization 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


where every Caijis 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 aVCM is


where NCais 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 Fof UMMG contains boundary conditions


as well as optimizing conditions


they induce linequalities


and tgoal functions


Domain of every variable γ, having place in polynoms Cai1,,Cail,Cj1,,Cjt, is defined by boundary condition


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 amultiplicity, obtained as a result of previous steps execution, is n, then when lower bound estimate of VCM of ais 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 amultiplicity increase, and branch may be terminated.

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


where k=NCa,γ¯jiare objects, corresponding to variables, while γ¯0is fictive object, corresponding to constants, having place in polynom. For example, polynom


is represented by multiset


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


as follows: object aconsists of n1objects a1,,nmobjects am.

In turn, technological interpretation of unitary rulesis generalization of the structural one and is as follows: production of one object (unit of resource) arequires n1objects (units of resource) a1,,nmobjects (units of resource) am.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 Rof such URs represents technological base (TB) of some social group, possessing represented by this set producing (manufacturing) equipment. If Rcontains l > 1 URs with identical head and different bodies, this means that one and the same object may be produced in lvarious ways (by lvarious devices, or by one and the same device, but by various methods, or by lvarious 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:


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 neandmt,whereeandtare fixed-name objects being cost and time measurement units (e.g., usdand 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,


(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, 3hour,23min,15sec, that after application of URs (14)–(16) will be transformed to one multiobject, 10953sec.

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 ntx,where xmay be manufacturing device name as well as assembled technical object name, while tis 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:


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


which means customer needs m1objects b1,,mkobjects bk.

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¯Sq, where


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

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


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


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¯Sq. 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 Runitary rules, defining costs of all necessary spare parts and other external (“outsourced”) resources. These URs may have form ane,where ais terminal object from R,while eis monetary unit, used for cost calculation. As may be seen, if one would eliminate from URs time-defining multiobjects, then ebecomes unique terminal object of the created scheme R, and set of terminal multisets generated by UMG S=aqRqwould 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:


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


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

If multiobjects 28mntcar,21mntbodyand60mntengineare eliminated from UR set presented in Example 10, then obtained UMG will generate one-element set {{Xusd}}.▪

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 completionrequires comparison of two resources collections—being in system’s ownership and necessary. In multigrammatical paradigm, this problem is solved quite simply.

Let Rbe technological base, while multiset v¯=m¯1b¯1m¯kb¯kis resource base of the system, that is, STS possesses m¯1objects b¯1,,m¯kobjects b¯k.As it is easy to see, order q=m1b1mlblmay be completed by this system, if there exists multiset vV¯Sqsuch that


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

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


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 vV¯Sq, 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 qcompletion2fuelcisternv¯while3fuelcisternvV¯Sq.▪

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 vV¯Sq,and vis 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


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 Rqbe scheme, corresponding to technological base of the system and order qin 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 Rand total resource v¯sustainable to impact Δv¯while completing order q, if


That is, despite impact there is at least one way of order completion. Otherwise, if there is no one TMS vV¯Sq, 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 nproducts, manufactured by STS, xiis amount of i-th product, and ciis its price. Profit, which producing STS would obtain, is


To produce one unit of i-th product, the system needs respective resources, namely, aijunits of the j-th resource, where j=1,,n, and nis total number of different resources, consumed by the system for production. There are b1, …, bnamount of resources available, and the problem is to maximize profit Cunder restrictions


where j=1,,n.

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


where x1,,xmare variables, and munitary rules


where i=1,,m, and aijis nonzero amount of j-th resource, needed for i-th product, while ciis its price. Filter Fcontains nboundary conditions


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


along with mvariable declarations


where i=1,,mand Miis maximal amount of i-th product, which may be manufactured by the system. As seen, terminal objects e1,,enare measurement units of corresponding resources, while terminal object eis price measurement unit. Nonterminal objects u1,,umrepresent products, and UMR (26) along with optimizing condition (29) represents order, while nURs (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




means that maximal profit is Cand it is gotten when STS produces p1units of the first product, …, pmunits of the m-th product. In general case


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

Example 6.Let POPE is


under restrictions


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 Rof the corresponding UMMG S=<q,R,F>includes UMR


as well as two URs:


Filter Fcontains two boundary conditions


one optimizing condition


as well as two variables declarations:


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

As seen,


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 ein 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,


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 firstapproach.

Let Rbe set of unitary rules containing, among others, kURs with one and the same head and different bodies:


where i-th alternative corresponds to i-th subject of considered technological base, able to produce object a,consuming for that purpose n1iobjectsa1i,,nmiiobjectsamii.To simplify and unify recognition of variant implemented, let us introduce kterminal objects s1,,sk, being names of corresponding subjects, and replace set (34) by


Let q=na,andRqis set of URs, containing UR


kURs (35), and all unitary rules from set R,excluding (35). Consider UMG Sq=aqRq. As seen, V¯Sqis set of terminal multisets, each corresponding to some variant of order qcompletion. If we establish filter Fqto select one and only one element of V¯Sq, transforming UMG Sqto FUMG Sq=aqRqFq,this element will be


where multiobject nsicorresponds to noperation cycles of subject siduring order qcompletion and every multiobject mjib¯jicorresponds to mjiterminal objects b¯ji, required for these cycles’ implementation. In this context, filter Fqmay contain boundary conditions, defining required resources limits, as well as optimizing conditions, defining some of terminal object b¯jimultiplicities 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 sibecomes the only winner, it takes all order to complete.

Example 7.Let us consider following unitary rules:


These URs being joined with URs, detailing nonterminal object accessories setfrom 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 Sq=aqRF,where q=3carandF=usd=min,then


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


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 s1,,sk)are not sufficient for the whole order completion. In this case, more rational may be the secondapproach when order is splitted between non-antagonistic (cooperating) competitors in such a way that the total amount of objects produced is distributed among subjects s1,,sk. This techniques may be modeled by unitary multimetagrammar Sq, which scheme Rqincludes unitary metarule


and unitary rules


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


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


As seen, terminal multisets, generated by UMMG S=aqRqFq,have form


where, according to (38)(40),


and thus values n1,,nkare parts of order q=na, distributed among subjects s1,,sk, respectively: s1will produce n1objects a, s2n2objects a, up to sk, which will produce nkobjects a.

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


If order q=10car,then Fq=car=100γ1100γ2100γ310Fq,where Fqmay contain boundary and optimizing conditions, selecting terminal multisets, for example, Fq=usd=minusd12800usd25000usd36600.According to such Fq, set of terminal multisets, generated by UMMG Sq=aqRqFq, may contain element of the form {10car,25600usd,14000usd1,5000usd2,6600usd3,5γ1,2γ2,3γ3,},

which corresponds to splitting order qin 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.

© 2018 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Igor Sheremet (December 27th 2018). Unitary Multiset Grammars an Metagrammars Algorithmics and Application, Enhanced Expert Systems, Petrică Vizureanu, IntechOpen, DOI: 10.5772/intechopen.82713. Available from:

chapter statistics

465total chapter downloads

3Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Introductory Chapter: Enhanced Expert System - A Long-Life Solution

By Petrică Vizureanu

Related Book

First chapter

Expert System for Identification of Sport Talents: Idea, Implementation and Results

By Vladan Papić, Nenad Rogulj and Vladimir Pleština

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us