Formal Properties and Implementation of BiDirectional Charts

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.