@inproceedings{lutz-1993-chart,
title = "Chart Parsing of Attributed Structure-Sharing Flowgraphs with Tie-Point Relationships",
author = "Lutz, Rudi",
booktitle = "Proceedings of the Third International Workshop on Parsing Technologies",
month = aug # " 10-13",
year = "1993",
address = "Tilburg, Netherlands and Durbuy, Belgium",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/1993.iwpt-1.14",
pages = "145--170",
abstract = "Many applications make use of diagrams to represent complex objects. In such applications it is often necessary to recognise how some diagram has been pieced together from other diagrams. Examples are electrical circuit analysis, and program understanding in the plan calculus (Rich, 1981). In these applications the recognition process can be formalised as flowgraph parsing, where a flowgraph is a special case of a plex (Feder 1971) . Nodes in a flowgraph are connected to each other via intermediate points known as tie-points. Lutz (1986, 1989) generalised chart parsing of context-free string languages (Thompson {--} Ritchie, 1984) to context-free flowgraph languages, enabling bottom-up and top-down recognition of flowgraphs. However, there are various features of the plan calculus that complicate this - in particular attributes, structure sharing, and relationships between tie-points. This paper will present a chart parsing algorithm for analysing graphs with all these features, suitable for both program understanding and digital circuit analysis. For a fixed grammar, this algorithm runs in time polynomial in the number of tie-points in the input graph.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="lutz-1993-chart">
<titleInfo>
<title>Chart Parsing of Attributed Structure-Sharing Flowgraphs with Tie-Point Relationships</title>
</titleInfo>
<name type="personal">
<namePart type="given">Rudi</namePart>
<namePart type="family">Lutz</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>1993-aug" 10-13"</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the Third International Workshop on Parsing Technologies</title>
</titleInfo>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Tilburg, Netherlands and Durbuy, Belgium</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<abstract>Many applications make use of diagrams to represent complex objects. In such applications it is often necessary to recognise how some diagram has been pieced together from other diagrams. Examples are electrical circuit analysis, and program understanding in the plan calculus (Rich, 1981). In these applications the recognition process can be formalised as flowgraph parsing, where a flowgraph is a special case of a plex (Feder 1971) . Nodes in a flowgraph are connected to each other via intermediate points known as tie-points. Lutz (1986, 1989) generalised chart parsing of context-free string languages (Thompson – Ritchie, 1984) to context-free flowgraph languages, enabling bottom-up and top-down recognition of flowgraphs. However, there are various features of the plan calculus that complicate this - in particular attributes, structure sharing, and relationships between tie-points. This paper will present a chart parsing algorithm for analysing graphs with all these features, suitable for both program understanding and digital circuit analysis. For a fixed grammar, this algorithm runs in time polynomial in the number of tie-points in the input graph.</abstract>
<identifier type="citekey">lutz-1993-chart</identifier>
<location>
<url>https://aclanthology.org/1993.iwpt-1.14</url>
</location>
<part>
<date>1993-aug" 10-13"</date>
<extent unit="page">
<start>145</start>
<end>170</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Chart Parsing of Attributed Structure-Sharing Flowgraphs with Tie-Point Relationships
%A Lutz, Rudi
%S Proceedings of the Third International Workshop on Parsing Technologies
%D 1993
%8 aug" 10 13"
%I Association for Computational Linguistics
%C Tilburg, Netherlands and Durbuy, Belgium
%F lutz-1993-chart
%X Many applications make use of diagrams to represent complex objects. In such applications it is often necessary to recognise how some diagram has been pieced together from other diagrams. Examples are electrical circuit analysis, and program understanding in the plan calculus (Rich, 1981). In these applications the recognition process can be formalised as flowgraph parsing, where a flowgraph is a special case of a plex (Feder 1971) . Nodes in a flowgraph are connected to each other via intermediate points known as tie-points. Lutz (1986, 1989) generalised chart parsing of context-free string languages (Thompson – Ritchie, 1984) to context-free flowgraph languages, enabling bottom-up and top-down recognition of flowgraphs. However, there are various features of the plan calculus that complicate this - in particular attributes, structure sharing, and relationships between tie-points. This paper will present a chart parsing algorithm for analysing graphs with all these features, suitable for both program understanding and digital circuit analysis. For a fixed grammar, this algorithm runs in time polynomial in the number of tie-points in the input graph.
%U https://aclanthology.org/1993.iwpt-1.14
%P 145-170
Markdown (Informal)
[Chart Parsing of Attributed Structure-Sharing Flowgraphs with Tie-Point Relationships](https://aclanthology.org/1993.iwpt-1.14) (Lutz, IWPT 1993)
ACL