Formal properties and implementation of bidirectional charts
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A bidirectional extension of the chart algorithm is proposed and its most relevant formal properties are investigated using an Earley like formalism and it is shown that the method presented here maintains those characteristics that were so much appreciated in monodirectional charts.
Abstract
Several theories of grammar currently converge toward inserting subcategorization information within lexical entries. Such a tendency would benefit from a parsing algorithm able to work from "triggering positions" outward. In this paper a bidirectional extension of the chart algorithm is proposed and its most relevant formal properties are investigated using an Earley like formalism. The question as to whether the proposed approach guarantees computational feasibility is then addressed and is answered affirmatively. Also, it is shown that the method presented here maintains those characteristics that were so much appreciated in monodirectional charts. Finally, from this analysis indications arc derived for an efficient implementation of the parsing algorithm.