Open access peer-reviewed chapter

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

By Igor Sheremet

Submitted: June 28th 2018Reviewed: September 26th 2018Published: November 21st 2018

DOI: 10.5772/intechopen.81698

Downloaded: 699


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


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

1. Introduction

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

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

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

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


2. Informal description

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


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


This set of constructions is of the form:


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


where niaimeans there are nipositions of type aiin this company.

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


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

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

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


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


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

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


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


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


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


3. Basic operations on multisets

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


Expression (26) is recorded as:


where vis called multiset, a1,,am—objects, n1,,nm—multiplicities of these objects, and n1a1,,nmam—multiobjects. Following Eq. (27), one may consider vas set of multiobjects; also, from substantial point of view, set a1amand multiset 1a11amare equivalent. Empty multiset, as well as empty set, is designated as . Multiplicity of object may be zero, what is equivalent to absence of this object in the multiset:


Fact that object aor multiobject nabelongs to multiset v(“enters v”) is designated by one and the same symbol :av,nav. Set βv=anavis called basis of multiset v.

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

Consider two multisets:


Result of their join (recorded as ) is multiset.


where ,anddesignate operations of set-theoretical join, intersection, and subtraction of two sets correspondingly, while designates operation of set-theoretical join of sets determined by underwritten conditions.

Result of v,vmultisets intersection (recorded as ) is multiset.


Result of v,vmultisets addition (recorded as bold +) is multiset.


Result of vmultiset subtraction from vmultiset (recorded as bold ) is multiset.


At last, result of vmultiset multiplication by integer number n(recorded as vn) is multiset.


(here integers’ usual multiplication is recorded as ×)

There are also two basic relations on multisets: inclusion () and strict inclusion ().

Multiset vis included to multiset v, that is, vv, if


and multiset vis strictly included to multiset v, that is, vv, if vv&vv.

Example 1.Let v1=3analyst2assistant,v2=4assistant1director, then


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

There are two types of conditions: boundary and optimizing.

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


where aand aare the objects, nis the integer number, and ρ<=. Chain boundary condition (CBC) is constructed from elementary by writing them sequentially:


where e1,,em+1are the objects or nonnegative integers, while ρ1,,ρmare the symbols of relations (<,=,).

EBC semantics is following. Let Vbe set of multisets, and vV. Multiset vsatisfies EBC n¯ρa, if naV, and n¯ρnis true. Similarly, vsatisfies EBC n¯, if n¯ρnis also true. At last, vsatisfies EBC aρa', if nav, nav, and nρn'is true. There is one addition to all listed definitions, concerning particular case, when navn'av, which is equivalent to n=0n'=0.

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


and vVis considered satisfying CBC (39), if it satisfies all EBC having place in Eq. (40).

Result of application of boundary condition bto SMS Vis recorded as Vb.

Example 2.Let V=v1v2,where v1=5analyst3assistant1director,v2=2assistant4director3employee,and boundary conditions are 2analyst4,assistant<employee,1directorassistant3,andanalyst=assistant<5.Table 1 contains result of application of listed boundary conditions to V.


Table 1.

Results of application of boundary conditions.

Optimizing condition has form a = opt,where ais the object, and optminmax. Semantics of this construction is following. Multiset vVsatisfies condition a=min, if for every vV, such that vv, multiplicity nin multiobject navis not greater, than multiplicity nin multiobject nav, that is, nn. Similarly, vVsatisfies condition a=max, if for every vV, such that vv, multiplicity nin multiobject navis not less, than multiplicity nin multiobject nav, that is, nn. If avav, we consider navnav, where n=0n=0.

Filter is join of boundary Fand optimizing Foptsubfilters:


where Fis set of boundary conditions, and Foptis set of optimizing conditions. Result of filtration of set of multisets Vby filter Fis denoted as VFand is defined by expression




and c1,,ckare EBC. As seen, set Vis filtered by boundary conditions, so there are selected multisets, satisfying all of these conditions, and intermediate result Vis then filtered by optimizing conditions, so, that multisets, satisfying all of them, are included to the final result.

Example 3.Consider set V=v1v2v3v4, where


Let F=1analyst32directoremployeeanalyst=minassistant=max.Then, according to Eqs. (41)(46),




Filtration is performed as follows:


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


4. Multiset grammars

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

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


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


where v(left part of the rule) and v(right part of the rule) are multisets, and v.Semantics of rule is as follows. Let v¯be multiset; with that we shall speak, that rule (48) is applicable to v¯, if vv¯, and result of its application is a multiset.


Speaking informally, if v¯includes v, then the last is replaced by v. Application of rule rRto multiset v¯is denoted as v¯rv¯, and any sequence v¯rrv¯is called generation chain.

Set of multisets, defined by MGs S=v0R, is denoted as VS. Iterative representation of MG semantics, that is, SMS VSgeneration by application of MG S, is the following:




As seen, function (53) implements application of rule vvto multiset v¯as described higher. As a result of i + 1-th step of generation, new SMS is formed by application of all rules rRto all multisets v¯Vi, and it is joined to SMS Vi. If multiset v¯is generated from multiset v¯by some sequence of such steps, it is denoted as v¯v¯.

VSis fixed point of the described process, that is, VS=Vi, where i. If for some finite iVi=Vi+1, then VS=Vi, and VSis finite. In the introduced notation,


VSincludes subset V¯sVsof the so-called terminal multisets (TMS) vV¯ssuch that πvr=for all rR, that is, no one multiset may be generated from terminal multiset. Set V¯Sis called final; final set consists of terminal multisets only.

Example 4.Let S=v0R, where v0=3eur4usd,

R=r1r2, where

r1is 2eur1usd1eur1gbp,

r2is 1eur2usd1eur2gbp.

As seen,


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


By analogy with classical string-generating grammars, multigrammars may be context-sensitive and context-free (CF). In the last one, left parts of all rules have form 1a, while in the first, there are no any limitations on both parts of rules, excluding, that left part must be nonempty multiset.


5. Unitary multiset grammars and metagrammars

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


they are written as:


Construction (56) is called unitary rule (UR), object a—its head, and unordered sequence (list) n1a1,,nmam—its body.

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

Iterative representation of UMG semantics, i.e., generation of SMS VS, where S=a0R,is following:




Here, A¯sis set of the so-called terminal objects, such that aA¯s, if and only if Rdoes not include URs, which head is a(i.e., ahas place only in the UR bodies). A¯sis subset of set Asof all objects, having places in scheme Rof UMG S. Multiset, generated by UMG S, all objects of which are terminal, is also called terminal multiset (as seen, this notion of TMS does not contradict to the defined higher regarding MGs). In Eq. (61), UR an1a1,,nmamis written in the angle brackets for unambiguity.

As seen, Eq. (59) defines VS—set of all multisets, generated by UMG S,—while Eq. (60) by condition βv¯A¯sprovides selection of V¯S—set of terminal multisets (STMS)—from VS.

Example 5.Consider unitary multigrammar S=companyR, where Rincludes following unitary rules:


According to Eqs. (57)(61),


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

FUMGs are triple S=a0RF, where a0, R, and Fhave the same sense, as above, and set of terminal multisets, generated by S, is defined as follows:


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

Example 6.Let S=companyRF, where Ris as in Example 5, while F=analyst>3analyst=min. Then, according to Eqs. (57)(62),


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

Unitary multimetagrammar Sis, as higher, triple a0RF, where a0is the title object, and Ris the scheme, containing unitary rules and so-called unitary metarules (UMR), while Fis the filter. Consider UMMG syntax and semantics.

Unitary metarule has the form:


where μiis the positive integer number, as in UMGs/FUMGs, or variable γΓ, where Γis the universum of variables. When μiis γiΓ, then it is called multiplicity-variable (MV). As seen, unitary rule is the simplest particular case of unitary metarule with all multiplicities μ1,,μmbeing constants. As in URs, object ain Eq. (55) is called head, while μ1a1,,μmam—body of metarule.

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


where optmaxmin. As seen, boundary condition (64) and optimizing condition (65) are the same, as in FUMG filters, while boundary condition (65), called variable declaration, defines set of values (domain) of variable γand is denoted lower as Nγ. If Fincludes subfilter FΓ=n1γ1n1nlγlnl, containing boundary conditions of form (66), then every combination of variable values n¯1Nγ1,,n¯lNγlprovides creation of one unitary multigrammar by substitution of n¯1,,n¯lto all unitary metarules, having places in scheme R, instead of multiplicities-variables being in their bodies; unitary rules, already having place in R, are transferred to new scheme, denoted Rn¯1n¯l, without any transformations. Every such UMGs generates set of terminal multisets, after what all these STMS are joined, and resulting set is filtered by filter F=FFΓ, containing all “FUMG-like” conditions (From the described, it is obvious nature of “multimetagrammar” notion—in mathematical logic, or “metamathematics,” “metalanguage” is language, used for description of another language, so “multimetagrammar” is “unitary-like” multigrammar, used for description of other unitary multigrammars by means of unitary metarules, variables-multiplicities, and boundary conditions, defining their domains.). As may be seen from this informal description, UMMGs are simple unified tool for compact representation of sets of FUMGs (for practically valuable problems, containing very large numbers of elements—millions and greater).

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


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

Let us now give strict definition of unitary multimetagrammar notion. UMMG S=a0RFdefines set of terminal multisets V¯Sin such a way:


and, at last, if ris aμ1a1,,μmam,then rn¯1n¯lis unitary rule.




As seen, according to Eqs. (75) and (76), all multiplicities-variables of unitary metarule aμ1a1,,μmamare replaced by their corresponding values from the tuple n¯1n¯l, while all multiplicities-constants (elements of positive integer numbers set N) remain unchanged. Evidently, if all μ1,,μmare constants, that is, if unitary metarule is UR, it remains unchanged.

Let us note, that multiplicities-variables area of actuality is whole UMMG scheme, that is, if there are n > 1 occurrences of one and the same variable γin different unitary metarules (and, of course, in one and the same unitary metarule), they all are substituted by one and the same value from the applied sequence n¯1n¯l.

Example 7.Let us consider UMMG S=<company,R,F>, where scheme Rcontains following three unitary metarules:


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


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




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


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


This form defines optimality of the generated terminal multisets through multiplicity-variable values, used while these TMS generation. Eq. (77) semantics is quite clear: select those TMS, which are generated by the help of value of variable γ, which (value) is minimal (maximal) among all other TMS, generated by γapplication. As seen, Eq. (77) extends optimality definition from only multiplicities-constants, having places in TMS, to also multiplicities-variables, having places in unitary metarules, applied while TMS generation.

Most simple formal definition of the verbally described sense of Eq. (77) optimizing condition may be as follows. Let us introduce lauxiliary terminal objects γ¯1,,γ¯lcorresponding variables γ1,,γl, having places in UMMG S=a0RF, i.e., unitary metarules and boundary condition (66). After that, let us add one new unitary metarule:


to scheme R, thus creating scheme R, which contains Eq. (78) and all elements of R, and substituting all optimizing conditions of the form γ=optby γ¯=optin filter F, thus converting them to the “canonical” form (65)—remember, γ¯is object not variable and, more, terminal object, because there is no any UR or UMR with head γ¯in R. Obtained filter will be denoted as F.

As seen now, UMMG S=a0RFgenerates terminal multisets of the form:




and TMS (79) will be selected to V¯S, if and only if TMS (80) satisfies all conditions, entering Fand concerning terminal objects ai1,,aik, as well as TMS n¯1γ¯1n¯lγ¯lsatisfies all optimizing conditions of the form γ¯i=optF, corresponding γi=optF..

It is not difficult to define V¯Sby subtracting from all vV¯Smultisets of the form n¯1γ¯1n¯lγ¯l, but from the practical point of view, it is more useful to consider not V¯Sbut V¯Sas a result of application of unitary multimetagrammar S: it is clear that all vV¯Scontain values n¯1,,n¯lof variables γ1,,γlas terminal objects γ¯1,,γ¯lmultiplicities, which computation is often main purpose of the mentioned application.

Example 8.As may be seen, problem, described in Section 2, is to obtain mquantity of laboratories, as well as nand lquantities of analysts and assistants, respectively, in one laboratory. Although Eqs. (18)(20) do not contain optimizing conditions of the form γ=opt,generating TMS like


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

So we shall use V¯Sas a result of S=a0RFunitary multimetagrammar application, even if Rdoes not include variable-containing optimizing conditions.

To finish with syntax and semantics of UMGs/UMMGs, let us note that class of unitary multigrammars is strict subclass of filtering unitary multiset grammars (UMGs FUMGs): every UMGs is FUMGs with empty filter. From the other side, FUMGs are strict subclass of unitary multiset metagrammars (UMGs FUMGs): every FUMGs is UMMGs without variable multiplicities and corresponding variable declarations inside filter.

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

© 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 (November 21st 2018). Multiset-Based Knowledge Representation for the Assessment and Optimization of Large-Scale Sociotechnical Systems, Enhanced Expert Systems, Petrică Vizureanu, IntechOpen, DOI: 10.5772/intechopen.81698. Available from:

chapter statistics

699total 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

Unitary Multiset Grammars an Metagrammars Algorithmics and Application

By Igor Sheremet

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