An Algorithm for Parsing Flow Graphs

Abstract

This report describes research about flow graphs - labeled, directed, acyclic graphs which abstract representations used in a variety of Artificial Intelligence applications. Flow graphs may be derived from flow grammars much as strings may be derived from string grammars; this derivation process forms a useful model for the stepwise refinement processes used in programming and other engineering domains. The central result of this report is a parsing algorithm for flow graphs. Given a flow grammar and a flow graph, the algorithm determines whether the grammar generates the graph and, if so, finds all possible derivations for it. The author has implemented the algorithm in LISP. The intent of this report is to make flow-graph parsing available as an analytic tool for researchers in Artificial Intelligence. The report explores the intuitions behind the parsing algorithm, contains numerous, extensive examples of its behavior, and provides some guidance for those who wish to customize the algorithm to their own uses.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1984
Accession Number
ADA142440

Entities

People

  • Daniel Carl Brotsky

Organizations

  • Defense Advanced Research Projects Agency

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Acceptability
  • Algorithms
  • Artificial Intelligence
  • Buildings And Structures
  • Computer Programming
  • Construction
  • Corporations
  • Engineering
  • Grammars
  • Guidance
  • Instructions
  • Leading Edges
  • Machines
  • Motivation
  • Simulations
  • Standards
  • Trailing Edges

Fields of Study

  • Computer science

Readers

  • Geospatial Intelligence and Artificial Intelligence Analytics
  • Graph Algorithms and Convex Optimization.
  • Software Engineering.

Technology Areas

  • AI & ML
  • AI & ML - DoD AI Strategy
  • AI & ML - Machine Learning Algorithms
  • AI & ML - Machine Translation