Rudi Lutz


2011

pdf
Algebraic Approaches to Compositional Distributional Semantics
Daoud Clarke | David Weir | Rudi Lutz
Proceedings of the Ninth International Conference on Computational Semantics (IWCS 2011)

2010

pdf
Semantic Composition with Quotient Algebras
Daoud Clarke | Rudi Lutz | David Weir
Proceedings of the 2010 Workshop on GEometrical Models of Natural Language Semantics

1993

pdf
Chart Parsing of Attributed Structure-Sharing Flowgraphs with Tie-Point Relationships
Rudi Lutz
Proceedings of the Third International Workshop on Parsing Technologies

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.