A Rewrite Rule Machine. Models of Computation for the Rewrite Rule Machine.

Abstract

A new model of computation, concurrent tree rewriting, is proposed as a bridge easily programmed Ultra High Level Languages (UHLLs) featuring implicit concurrency, and an advanced parallel architecture of unprecedented performance, the Rewrite Rule Machine (RRM) architecture. At the highest level of abstraction, computation is understood as rewriting a tree at multiple sites concurrently. Less abstractly, such a (possibly very large) tree can be partitioned into fragments that are assigned to different processors, with each processor doing concurrent rewriting on its own fragment of the tree; this gives the second level, partitioned concurrent rewriting. After introducing the basic concepts and properties of the model, we discuss tradeoffs between tree and directed acyclic graph (dag) data representations; we also study partitioned concurrent rewriting, including tree and rule partitioning, and discuss evaluation strategies as a flexible control mechanism for concurrent rewriting. The mathematical definitions are gathered in an appendix. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1986
Accession Number
ADA171089

Entities

People

  • Claude Kirchner
  • Joseph Goguen
  • José Meseguer

Organizations

  • SRI International

Tags

Communities of Interest

  • Autonomy
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Artificial Intelligence
  • Boundaries
  • Computations
  • Computer Languages
  • Computer Programming
  • Computer Science
  • Computers
  • Computing System Architectures
  • Efficiency
  • Formal Languages
  • High Level Languages
  • Information Science
  • Language
  • Natural Languages
  • Object Oriented Programming
  • Programming Languages
  • Rational Numbers

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computational Linguistics
  • Graph Algorithms and Convex Optimization.