An Algorithm for Parsing Flow Graphs

Title: en_US An Algorithm for Parsing Flow Graphs
Creator: en_US Brotsky, Daniel Carl
Date: 2004-10-20T20:03:27Z
Date Available: 2004-10-20T20:03:27Z
Date Issued: en_US 1984-03-01
Identifier: en_US AITR-704
uri: http://hdl.handle.net/1721.1/6866
Abstract: en_US 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.
Extent: en_US 152 p.; 5446139 bytes; 3922057 bytes
Format: application/postscript; application/pdf
Language: en_US
Relation: en_US AITR-704