Open access peer-reviewed chapter

Multi-Agent Implementation of Filtering Multiset Grammars

Written By

Igor Sheremet

Submitted: June 18th, 2020 Reviewed: July 1st, 2020 Published: July 25th, 2020

DOI: 10.5772/intechopen.93303

Chapter metrics overview

432 Chapter Downloads

View Full Metrics


Chapter is dedicated to the application of multi-agent technology to generation of sets of terminal multisets (TMS) defined by filtering multiset grammars (FMG). Proposed approach is based on creation of multi-agent system (MAS), corresponding to specific FMG in such a way, that every rule of FMG is represented by independently acting agent. Such MAS provides high-parallel generation of TMS and may be effectively used in any proper hardware environment. Directions of further development of the proposed approach are discussed.


  • multi-agent systems and technologies
  • multisets
  • multiset grammars
  • filtering multiset grammars
  • parallel computations

1. Introduction

Filtering multiset grammars (FMG) were developed as a result of multiset-based deep integration and convergence of classical mathematical programming and modern knowledge engineering for compact, flexible and natural representation of wide spectrum of combinatorial problems and their solution by application of unified algorithmics [1, 2, 3, 4, 5, 6].

One of the advantages of FMG is natural parallelism of generation of multisets (MS) due to the possibility of independent application of rules to the currently available MS. Such feature being supported by appropriate hardware is a very promising background for the effective implementation of FMG and hence effective solution of the aforementioned problems. However, the “brutal force” approach, demanding on the extensive parallelism, is not suitable here because of evident cost restrictions. More attractive looks such techniques which would be based on the “branches and bounds” logics providing cut off sets of multisets (SMS) which provably do not contain terminal multisets (TMS), defined by FMG, without their generation.

To develop such perspective approach we propose to apply multi-agent technology (MAT) [7, 8, 9, 10, 11, 12] as a basis for implementation of the aforementioned techniques. The main idea of the suggested method of TMS generation is representation of the generating engine as a multi-agent system (MAS), which includes:

  1. N agents, each corresponding to one rule from FMG scheme;

  2. one agent corresponding to FMG filter;

  3. one supervising agent, accumulating generated TMS, satisfying filter.

This MAS operates in such a way that every rule is applied (i.e. agent becomes active) as soon as there occurs multiset, matching this rule. By this approach maximally possible degree of parallelism is achieved.

Structure of the chapter is as follows. Section 2 contains main definitions and notions of the multigrammatical framework, necessary for further considerations. Proposed techniques of the multi-agent implementation of multisets generation is introduced in Section 3. Directions of future development of these techniques are discussed in the conclusion.


2. Basic notions and definitions of the multigrammatical framework

Classical theory of sets is based on notion of set as an unordered collection of mutually distinguishable elements. Basic assumption of theory of multisets is that aforementioned collection may contain indistinguishable (identical) elements:


Record (1) is usually represented as


where v is called multiset, niaimultiobjects (MO), aiobjects, ni– their multiplicities, for alli=1,,m. According to (2), multiset may be considered as a set of multiobjects, and, in fact, multiset 1a11am and set a1am represent one and the same collection. Seta1am, denoted as βv, is called basis of multisetv. Both empty multiset and empty set are denoted as Ø.

Zero multiplicity of some object is equivalent to the absence of this object in multiset, i.e.


Fact, that object aenters MSv (or MSvincludes object a), is denoted as av. Symbol “” is also used to denote, that MOna enters MSv (MSv includes MOna):nav. Structure of the left operand determines what kind of relation is referred in every particular case. Similarly, symbol “” is used to denote, that object a (multiobject na) does not enter multiset v. Due to (3),av and 0av are equivalent.

Number v=m is called dimensionality of MSv, and number


is called power of MSv.

Two basic relations on multisets – inclusion (“”) and strict inclusion (“”) – are defined as follows.

MSv is included to MSv', if


i.e. for every MOna entering MSv there exists MOna, which multiplicity n is not less than n. There may be also nav such that av (as seen, this does not contradict (5), because0av and 0<n).

If vv and vv, then MSv is strictly included to MSv, that is denoted vv.

MSv, which is included to MSv, is called submultiset of MSv; MSv, which is strictly included to MSv, is called strict submultiset of MSv.

Let us illustrate introduced notions by the following example, where, as in all other examples, having place in this chapter, objects will be represented by strings in brackets.

Example 1. Let


As seen, according to (5), vv and vv'.∎

Three basic operations on multisets are multiplication by a constant, addition, and subtraction, which are denoted by bold symbols ∗, + and − respectively. Semantics of these operations is defined by use of the well known set-theoretical operations (join and intersection), as well as arithmetic operations on integer numbers:


where “×” denotes multiplication of integer numbers;


Along with these operations, we shall use set-theoretical operations on multisets – join and intersection, – denoted respectively by bold symbols ∪ and ∩, different from ∪ and ∩:


We have used equivalence between av and 0av in (9).

Example 2. Letv and v be as in Example 1. Then


Common feature of all described operations, which are known from theory of multisets [13, 14], is that their operands are multisets and integer numbers. Unlike them, following operation called “filtration” applies set of multisets (SMS) as the first operand and so called “filter”, being set of conditions, as the second operand. Filtration is denoted as VF, where V is filtrated SMS, F is filter, and “” – symbol of operation.

Conditions entering filter F may be boundary and optimizing.

Boundary conditions (BC) are recorded as aθn, where θ><=. Multiset v satisfies BCaθn, if mav and mθn is true (as everywhere, av is equivalent to 0av).

Let F=bc1bck be a filter, containing only boundary conditions.



Example 3. Let V=v1v2v3, where


and F=usd>3rur12. Then


Optimizing conditions (OC) are recorded asa=opt, where optmaxmin. Multiset vV satisfies OCa=max, if nav and all multisets vVv satisfy boundary condition an. Similarly, multiset vV satisfies OCa=min, if nav and all multisets vVv satisfy boundary condition an.

Let Fopt=oc1ocl be filter, containing only optimizing conditions. Then, similarly to (6),


Example 4. Let V be the same as in Example 3, and

Fopt=usd=maxrur=min. Then


If filter F contains both boundary and optimizing conditions, i.e.




i.e. result of filtering set of multisets V by filter F is obtained by application of boundary subfilter F toV, after what resulting SMS is filtered by optimizing subfilter Fopt.

Application of filters, containing boundary and optimizing conditions, is illustrated by Figure 1.

Figure 1.

Filters application.

Considered operations on multisets and their sets make it possible to define syntax and semantics of family of multiset grammars.

Background of this family is notion of multiset grammar as a couple S=v0R, where v0 called kernel is multiset, and R called scheme is finite set of so called rules. Set of all objects used in kernel and scheme of MGS is denoted as AS.

RulerR is a construction


where multisets v and v are called respectively left part and right part of the rule r, and “” is divider. The only restriction on left and right parts of the rule isvØ.

If vv, then result of application of rule r to multiset v is multiset


Speaking informally, (16) defines, that if left part of the rule, i.e. multiset v, is included to MSv, then v is replaced by right part of this rule, i.e. multiset v. Result of application of rule r to multiset v is denoted as


and it is said, that MSv' is generated from MSv by application of rule r. If left part v is not included to MSv, result of application r to v is empty MSØ.

Set of multisets, generated by application of multigrammarS=v0R, or, just the same, defined by this multigrammar, is recursively created as follows:


As seen, VS includes all multisets, which may be generated from MSv0 by sequential application of rules rR, and VS is fixed point of the sequence V0,V1,,Vi,, so


In general case VS may be infinite.

If MSv' may be generated from MSv by application of some sequence (chain) of rules entering scheme R, it is denoted as


and, if so,


Multiset vVS is called terminal multiset (TMS), if


i.e. no any rule rR may be applied to this multiset. Set of terminal multisets (STMS) defined by multiset grammar S is denoted VS¯. Evidently,


Example 5. Let S=v0R, where kernel


and scheme R=r1r2, where r1 is


and r2 is


According to (18)–(19),


As seen, this MG provides generation of all possible collections of Euros, US dollars, and Russian rubles, which may be obtained from the initial collection v0 by sequential currency exchanges, which parameters are fixed by rules r1 and r2 (2 Euros may be exchanged to 4 US dollars, 2 US dollars and 3 Russian rubles may be exchanged to 2 Euros).∎

Generalized scheme of application of multiset grammars is presented at Figure 2.

Figure 2.

Application of multiset grammars.

Due to the fact, that multiobjects contain both numerical and symbolic components (multiplicities and object names), generation of multisets provides knowledge-driven numerical computation, that creates a lot of new opportunities for simple formalizing and effective solution of various sophisticated practical problems with hard combinatorial background. To implement such opportunities, so called filtering multiset grammars were proposed in [1, 2]. FMG are such generalization of MG, that integrate two basic concepts—generation of set of multisets and selection from it such MS, that satisfy some logical conditions, joined to filter.

Filtering multiset grammar is a triple S=v0RF, where v0 and R are, as above, kernel and scheme, while F is a filter, including boundary and optimizing conditions, defining multisets, which would be selected from the set of TMS, generated by MGv_0R, i.e.


Verbally, Vs is subset of V¯v0R, which includes only such elements of this set, that satisfy filter F. Generalized scheme of application of filtering multiset grammars is presented at Figure 3.

Figure 3.

Application of filtering multiset grammars.

After description of syntax and semantics of filtering multiset grammars we may move to their implementation issues, which background are multi-agent technologies.


3. Basic techniques of the multi-agent implementation of multisets generation

Due to granularity and natural internal parallelism of multigrammatical representation it is perspective to try to use multi-agent paradigm as a background for implementation of the FMG application engine (AE), providing generation of multisets.

We shall use scheme, depicted at Figure 4, as a basis for primary multi-agent implementation of FMG AE. Proposed multi-agent system implementing FMGS=v0RF, contains l=R agents r1,,rl, each corresponding to one rule from set R (everywhere below we shall denote rules and implementing them agents by the same symbols); one agent F, implementing filter F; one agent G, providing supervision on other agents interaction (in fact, implementing ubiquitous generation by application of rules to multisets, generated at previous steps). Agent G uses storage VS for accumulation of all generated terminal multisets, satisfying filter F. Also G operates storage V, containing current set of generated multisets, which are not yet transferred to other agents. Initial state of V is v0. Agents communicate via network N.

Figure 4.

Multi-agent system implementing FMG.

Described multi-agent system is operating according to the definition of mathematical semantics of FMG (15)–(26). Set of messages, which are circulating between the agents, is represented in Table 1.

1Grijvj – number of MS,vØ
2riGjvv – result of application of rule
ri to MSv
3riGjØRule ri is not applicable to v
4Gjv,jvAs 1
5FGj1jth MS satisfies filter F
6FGj0jth MS does not satisfy filter F

Table 1.

Set of MAS messages.

All messages are couples, the first components of which are numbers of multisets, processed by the agents, and every MS has its unique number. Assigning numbers to multisets is performed by agent G. Current maximal number is denoted J. Also agent G uses variable Z, which value is set of couples jn, where n is number of agents ri which until current moment have not sent to G messages with results of application of corresponding rule to jth MS.

Agent G sends couple jv to all agents ri. After this, G joins to the current value of variable Z couple jl. Every agent ri, receiving message jv from agent G, tries to apply v to rule ri. If application is possible, ri sends to G message j,v, where v is result of application of rule ri to MSv. Otherwise ri sends to G message jØ. Agent G, receiving message jv, where vØ, assigns J new value J+1, and sends message Jv to all agents. Also couple Jl is joined to Z, and couple jqZ is eliminated from set Z, that means at least one rule was applied to jth MS, so this multiset is non-terminal. If agent G receives message jØ from ri, that means rule ri was not applied to jth multiset, and jqZ is replaced by jq1. If now j0Z, that means no one rule was applied to jth MS, that’s why it is terminal, and, according to FMG semantics, it must be filtered. So agent G sends couple jv to agent F, which provides testing, whether v satisfies boundary subfilter FF. If testing is successful, agent F sends to agent G message j1, otherwise—message j0. In the case j1 couple jv is joined to the current value of variable Vs. After no active agents ri remain, agent G applies optimizing subfilter FoptF to the aforementioned current value Vs, eliminating from it all multisets, which do not satisfy Fopt. Final value of variable Vs is exactly set of terminal multisets, defined by FMGS=v0RF.

As may be seen, proposed multi-agent system provides generation and filtration of multisets by parallel operation of all agents, entering this MAS.

However, there are some evident bottlenecks, limiting speed of multisets generation. Most essential of such bottlenecks are massive transmissions of multiply repeated sets of multiobjects via MAS communication network. To reduce such transmission it is possible not to send MO to agents ri such, that corresponding them rules are applicable to multisets, having place in the storage V, and this applicability may be recognized directly by agent G. If such opportunity may be implemented, only those agents ri, which, possibly, may apply corresponding rules to current MS, would receive it. By this measure, traffic on MAS communication network may be reduced sharply.

To implement proposed logics, we shall introduce auxiliary database L, which elements would be couples ai1n1iknk, where a is name of object, and in couples in, entering the set, which is second component of the couple, integer i is number of the rule, which left part contains multiobject na.

Example 6. Let scheme R=r1r2, where r1 is


and r2 is


Then L=<eur<19><25>><rur<23>>.

Database L has such internal organization, that there exists associative index, providing direct selection of couple aw for object name a. To reduce search in the selected list of couples in, it may be created as ordered by increase of multiplicities n. Let v=n1a1nmam be a current multiset processed by agent G, and Q=a1n1amnm is set of queries to database L, each providing selection of couples aij1ijkii, such that npini. It is clear, that only in this case rules rj1i,,rjkii may have opportunity to be applied to MSv, and, totally, only those rules, in which all multiobjects from their left parts have multiplicities hot greater than those of the same objects having place in v. So there is an evident criterion for selection of rules, which may be applicable to the current multiset v.

Statement 1. Let ai1N1aipNp be a set, selected from database L by query Q=a1n1amnm, corresponding to multiset v=n1a1nmam, and nj1aj1njsajs be the left part of rule r. Then r may be applicable to v, if


As seen, proposed associative organization of set of left parts of rules entering scheme R provides fast selection of sets of rules, which may be applied to the current multiset.

Let us consider further enhancement of FMG application engine, based on the multi-agent technology.

First of all, it is evident, that it is not necessary to send all multiobjects of multiset v, to which ruleri is applicable, to agent ri, because replacement of left part of this rule by its right part is local operation, regarding in general case relatively small number of multiobjects in the processed multiset v, while all the rest MO remain unchanged. So it is sufficient to send to agent ri only tuple f1ni1ftnit of multiplicities of objects ai1,,ait, in MSv, such that tuple A=ai1ait is ordered lexicographically set of objects, having place in both left and right parts of rule r, and signs fi before multiplicities nij of objects aij, having place in left side of rule r, are “–”, while all other are “+”. Receiving this tuple, agent r provides computation of tuple ni1nit, where nj=nj+fjnij,j=1,,t. (There may be particular case, when some objects do enter both left and right parts but this singularity is simply handled by positioning to the jth place of tuple A number n+n, where n is multiplicity of object aij in the left part, and n–its multiplicity in the right part of rule r).

Example 7. Let v=5eur10usd7rur18pound, and r is 3eur2rur5usd. Because set of lexemes, entering this rule, is ordered lexicographically as eurrurusd so tuple, sent by agent G to agent r, would be 5710 and agent r would sent to agent G tuple 537210+5=2515, and, thus, result of vrv would be v=2eur15usd5rur18pound. As seen, multiplicity of object pound is not transferred to agent r, because this object does not enter rule r.∎

Proposed techniques provides further reduction of traffic on MAS communication network and, thus, total time of generation of STMS, defined by FMG.

Application of the described MAS-based generation of STMS is flexible as it is only possible: due to granularity of multigrammatical knowledge representation local corrections of FMG by replacement of one rules by another are easily reflected by corresponding replacement of only concerned agents without touching the other. The same may be done with FMG filters. Such flexibility provides the simplest implementation of the most practically useful “what-if” regimes of application of MG-centered knowledge-based decision support systems.


4. Conclusion

Proposed techniques of application of multi-agent technology to the high-parallel generation of sets of multisets, defined by filtering multiset grammars, provides essential growth of speed of creation of STMS. However, there are some evident ways of further enhancement of FMG implementation upon this background:

  • development of methods of matching constructed MAS to real homogeneous or heterogeneous hardware in such a way that delays, caused by information exchange between agents, would be minimal;

  • development of more efficient MAT application techniques concerning some more particular cases of MG – first of all, filtering context-free multiset grammars as well as filtering unitary MG and unitary multiset metagrammars;

  • design of special-purpose computing environments suitable for direct implementation of FMG and other dialects of MG family;

  • development of MAT-based techniques of implementation of algorithmics of unitary multiset metagrammars as most practically useful tool of the MG family.



Author is grateful to Prof. Fred Roberts and Prof. Alexey Gvishiani for useful discussions.


  1. 1. Sheremet IA. Recursive Multisets and their Applications. Moscow: Nauka; 2010. p. 292 (in Russian)
  2. 2. Sheremet IA. Recursive Multisets and their Applications. Berlin: NG Verlag; 2011. p. 249
  3. 3. Sheremet IA. Multiset analysis of consequences of natural disasters impacts on large-scale industrial systems. Data Science Journal. 2018;17(4):1-17. DOI: 10.5334/dsj-2018-004
  4. 4. Sheremet I. Multiset-based knowledge representation for the assessment and optimization of large-scale sociotechnical Systems. In: Vizureanu P, editor. Enhanced Expert Systems. London: IntechOpen; 2019. DOI: 10.5772/intechopen.81698. Available from:
  5. 5. Sheremet I. Unitary multiset grammars and metagrammars algorithmics and applications. In: Vizureanu P, editor. Enhanced Expert Systems. London: IntechOpen; 2019. DOI: 10.5772/intechopen.82713. Available from:
  6. 6. Sheremet I. Multiset-based assessment of resilience of sociotechnological systems to natural hazards. In: Tiefenbacher J, editor. Natural Hazards—Risks, Exposure, Response, and Resilience. London: IntechOpen; 2019. DOI: 10.5772/intechopen.83508. Available from:
  7. 7. Shoham Y, Leyton-Brown K. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press; 2009. p. 532
  8. 8. Schatten M, Tomicic I, Duric BO. Multi-agent modeling methods for massively multi-player on-line role-playing games. In: 2015 38th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO). 2015
  9. 9. Waldrop MM. Free agents: Monumentally complex models are gaming out disaster scenarios with millions of simulated people. Science. 2018;360(6385):144-147
  10. 10. Sycara KP. Multiagent systems. AI Magazine. 1998;19(2):79-92
  11. 11. Yeoh W, Yokoo M. Distributed problem solving. AI Magazine. 2012;33(3):53-65
  12. 12. Van der Hoog S. Deep learning in (and of) agent-based models: A prospectus. 2018. ArXiv: 1706.06302
  13. 13. Petrovskiy AB. Spaces of Sets and Multisets. Moscow: Editorial URSS; 2003. p. 248 (in Russian)
  14. 14. Petrovskiy AB. Theory of Measured Sets and Multisets. Moscow: Nauka; 2018. p. 360 (in Russian)

Written By

Igor Sheremet

Submitted: June 18th, 2020 Reviewed: July 1st, 2020 Published: July 25th, 2020