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

Abstract

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.

Keywords

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

1. Introduction

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

Vi+1=VivVian1a1nmamRnav{vna+n{n1a1nmam}}E1

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 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=optF, where a is object, optmaxmin, 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 an1a1,,nmam, where w as well as c is multiset n1a1nmam.

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,FTglobal; variables v,Rlocal;

             v;FT;

            /* initial values of optimized multiplicities settings */

            do a=optF;

            case opt:

                       {min:if kakF

                                      then FT:amink;

                                      else FT:aminMAX;

                       max : if kakF

                                      then FT:amaxk;

                                      else FT:amax0;

                       };

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

                       return;};

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

            do navwhere a is terminal object;

                if kakF&n>k/* n already exceeds higher bound */

                    then return;

                if aminlFT

                    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 navwhere a is non-terminal object;

            do awR; /* all non-terminal object a alternatives */

                 call Gvna+nw,R;

             end aw;

             end;

end G;

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

variables v, x local;

            do nav;

                 if kakF

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

                                  then return;

                 if aminlFT

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

                                  then return;

                 if amaxlFT

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

                                  then return;

            end na;

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

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

            do aoptlFT

                 do nav;

                      if ln/* at least one value corrected */

                          then FT:aoptlaoptn/replacement/x1};

                     /flag reset/

                 end na;

            end opt;

            if x=0 /* no values corrected */

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

                 else Vv;/* 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 kakF,then initial value of object a multiplicity would be kin 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=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 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 namultiplicity nalready exceeds upper bound kof boundary condition kakF. (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 aminlFT(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 nawith 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 aoptlFT; 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 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 TMSG 1a0RFis result of TMSG call. Then

TMSG1a0RF=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=Cai1ai1Caimaim,E3

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 a VCM is

Ca=nia+i=1NCaniaγ1ili1aγmiilimia,E4

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 F of UMMG contains boundary conditions

k1ai1k1,.klailklE5

as well as optimizing conditions

aj1=opt1,.ajt=optt,E6

they induce l inequalities

k1Cai1k1,.klCailkl,E7

and t goal functions

Caj1optj1,.Cajtoptjt.E8

Domain of every variable γ, having place in polynoms Cai1,,Cail,Cj1,,Cjt, 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: Cais represented as

va=n0aγ¯0n1aγ¯0e11aγ¯11e1m1aγ¯m11nkaγ¯0ek1aγ¯1kekmkaγ¯mkk,E10

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

Ca=5+3γ12γ24+γ25γ3E11

is represented by multiset

va=5γ¯03γ¯02γ¯14γ¯31γ¯05γ¯21γ¯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

an1a1,,nmamE13

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

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

car1body,1engine,1transmission,4wheel,1fuelcisterm,body1frame,1frontglass,1backglass,1enginecover,1baggageplace,2firstdoor,2backdoor,engine1motor,1coolingsystem,1accumulator.

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

eur1.15usd,E14
hour60mnt,E15
mnt60secE16

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

car28mntcar,3000usd,1body,1engine,1transmission,4wheel,1fuelcisterm,body21mntbody,2000usd,1frontglass,1backglass,1enginecover,1baggageplace,2firstdoor,2backdoor,engine60mntengine,6000usd,1motor,1coolingsystem,1accumulator.

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=m1b1mkbk,E17

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

Sq=aqRq,E18
Rq=Raqm1b1mkbkE19

(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

order3car,E20

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

V¯Sq=84mntcar63mntbody180mntengine27000usd,3transmission,12wheel,3fuelcistern,3frontglass,3backglass,3enginecover,3baggageplace,6firstdoor,6backdoor,3motor3coolingsystem3accumulator.

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 R unitary rules, defining costs of all necessary spare parts and other external (“outsourced”) resources. These URs may have form ane,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=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:

transmission100usd,wheel50usd,accumulator10usd.

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

84mntcar63mntbody180mntengineXusd,

where X is 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 {{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¯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

vv¯,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 vV¯satisfying (21), then system is not able to complete q.

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

v¯=6transmission,10wheel,2fuelcistern,7frontglass,9backglass,180mntcar,240mntbody,600mntengine,1000000eur,500000usd

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 q completion2fuelcisternv¯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 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¯Sq=v¯vvV¯Sq.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 Rqbe 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

vV¯Sqvv¯Δv¯.E23

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

C=i=1mcixi.E24

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 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=1maijxibj,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

qx1u1,,xmum,E26

where x1,,xmare variables, and m unitary rules

uiai1e1,,ainen,cie,E27

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

ejbj,E28

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

e=max,E29

along with m variable declarations

0xiMi,E30

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 e is price measurement unit. Nonterminal objects u1,,umrepresent 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

VS¯=v1vt,E31

where

l1e1lnenCep1x¯1pmx¯mVS¯E32

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

VS¯>1,E33

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

Example 6. Let POPE is

2x1+3x2max

under restrictions

3x1+2x210
5x1+3x218.

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

qx1u1,x2u2,

as well as two URs:

u13e1,5e1,2e,
u22e1,3e2,3e.

Filter F contains two boundary conditions

e110,
e218,

one optimizing condition

e=max,

as well as two variables declarations:

0x110,
0x210,

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

As seen,

V¯S=10e116e210e2x¯12x¯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,

transmission100usd,wheel50usd,accumulator10usd.

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:

an11a11,,nm11am11,an1ka1k,,nmkkamkk.E34

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 k terminal objects s1,,sk, being names of corresponding subjects, and replace set (34) by

a1s1,n11a11,,nm11am11,a1sk,n1ka1k,,nmkkamkk.E35

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

aqna,E36

k URs (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 q completion. If we establish filter Fqto select one and only one element of V¯Sq, transforming UMG Sqto FUMG Sq=aqRqFq,this element will be

nsim1ib¯1imliib¯lii,E37

where multiobject nsicorresponds to n operation cycles of subject siduring order q completion 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:

car1first,30mntcar,2800usd,1accessoriesset,car1second,40mntcar,2700usd,1accessoriesset,car1third,45mntcar,2500usd,1accessoriesset.

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 Sq=aqRF,where q=3carandF=usd=min,then

V¯Sq=1thirdXusd135mntcar,

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

V¯Sq=,

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 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 s1,,sk. This techniques may be modeled by unitary multimetagrammar Sq, which scheme Rqincludes unitary metarule

aqγ1b1,,γkbk,E38

and unitary rules

b11a,n11a11,,nl11al11,bk1a,n1ka1k,,nlkkalkk,E39

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

a=n,E40

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

0γin.E41

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

nan1γ¯1nkγ¯km1ib¯1imliib¯lii,E42

where, according to (38)(40),

i=1kni=n,E43

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 R from Example 7 to the following:

orderγ1first,γ2second,γ3third,first1car,2800usd,2800usd1,1accessoriesset,second1car,2500usd,2500usd2,1accessoriesset,third1car,2200usd,2200usd3,1accessoriesset.

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

Acknowledgments

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

117total chapter downloads

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