Parallelism analysis in rule-based systems using graph grammars

  • D. Moldovan
  • F. Parisi-Presicce
Part II Technical Contributions
Part of the Lecture Notes in Computer Science book series (LNCS, volume 291)


The processing speed of Rule-Based Systems (or Production Systems PS) may be increased by using parallel processing techniques. In this paper we present a model for studying and exploiting parallelism in PS which is based on graph grammar theory. First, interdependencies between production rules are identified and then used to minimize the PS search space and to map the PS into multiprocessors.

Key words

gluing diagrams dependencies search tree 


  1. [1]
    R.Davis and J.King, An overview of Production Systems, in Machine Intelligence vol 8 (eds. E.W.Elcock and D.Michie) 1977.Google Scholar
  2. [2]
    H. Ehrig, Introduction to the Algebraic Theory of Graph Grammars, Lect. Notes in Comp. Sci. 73, Springer-Verlag, 1979, pp.1–69Google Scholar
  3. [3]
    D.Moldovan and V.Dixit, Minimal State Space Search in Production Systems, Technical Report CRI-87-19, USC Dept. of Electr. Eng., January 1987Google Scholar
  4. [4]
    D.Moldovan, RUBIC: A Multiprocessor for Rule-Based Systems, Technical Report CRI-87-32, to appear in IEEE Transactions on Systems, Man and Cybernetics.Google Scholar
  5. [5]
    H. Ehrig and B.K. Rosen, Parallelism and Concurrency of Graph Manipulations, Theor. Comp. Sci. 11 (1980) 247–275.CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1987

Authors and Affiliations

  • D. Moldovan
    • 1
  • F. Parisi-Presicce
    • 2
  1. 1.Dept. of Electrical Engineering — Systems 0781University of Southern CaliforniaLos Angeles
  2. 2.Dept. of Mathematics 1113University of Southern CaliforniaLos Angeles

Personalised recommendations