\relax 
\citation{Lambek:sentstruct}
\citation{Colmerauer:mgs,Pereira+Warren:DCGs,Pereira+Warren:ED}
\citation{Shieber:inference,Rounds+Manaster-Ramer:fg,Carpenter:logic}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {1}INTRODUCTION}{1}}
\newlabel{sec:intro}{{1}{1}}
\citation{Bancilhon+Ramakrishnan:amateur,Naughton+Ramakrishnan:bottom-up}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {2}BASIC NOTIONS}{2}}
\newlabel{sec:pasd}{{2}{2}}
\citation{ka65,y67}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {2.1}A First Example: CYK Parsing}{3}}
\newlabel{sec:cyk}{{2.1}{3}}
\citation{Naughton+Ramakrishnan:bottom-up}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {1}{\ignorespaces The CYK deductive parsing system.}}{4}}
\newlabel{fig:cyk-sys}{{1}{4}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {2.2}Proofs of Correctness}{5}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {3}DEDUCTIVE PARSING OF CONTEXT-FREE GRAMMARS}{5}}
\newlabel{sec:cf}{{3}{5}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {3.1}Pure Top-Down Parsing (Recursive Descent)}{5}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {2}{\ignorespaces The top-down recursive-descent deductive parsing system.}}{6}}
\newlabel{fig:td-sys}{{2}{6}}
\newlabel{eg-sent}{{1}{6}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {3}{\ignorespaces An example context-free grammar.}}{7}}
\newlabel{fig:toy}{{3}{7}}
\@writefile{toc}{\string\contentsline\space {subsubsection}{\string\numberline\space {3.1.1}Proof of Completeness}{7}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {3.2}Pure Bottom-Up Parsing (Shift-Reduce)}{8}}
\citation{e70}
\citation{Lang:74,Billot+Lang:shared}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {4}{\ignorespaces The bottom-up shift-reduce deductive parsing system.}}{9}}
\newlabel{fig:bu-sys}{{4}{9}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {3.3}Earley's Algorithm}{9}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {5}{\ignorespaces Summary of parsing algorithms presented as deductive parsing systems. (In the axioms and goal items of Earley's algorithm, $S'$ serves as a new nonterminal not in $N$.)}}{10}}
\newlabel{tab:summary}{{5}{10}}
\citation{e70}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {4}DEDUCTIVE PARSING FOR OTHER FORMALISMS}{11}}
\newlabel{sec:others}{{4}{11}}
\citation{Colmerauer:mgs}
\citation{Pereira+Warren:DCGs}
\citation{Shieber:inference,Carpenter:logic}
\citation{Shieber:inference}
\citation{Pereira+Warren:DCGs}
\citation{Shieber:criteria}
\citation{Bresnan+Kaplan:lfg,Pereira+Warren:ED,Shieber:inference}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {4.1}Augmented Phrase-Structure Formalisms}{12}}
\newlabel{sec:augmented}{{4.1}{12}}
\citation{Shieber:restriction,Shieber:inference}
\citation{Sato+Tamaki:patterns}
\newlabel{sec:offline}{{4.1}{13}}
\citation{ades-steedman}
\citation{ades-steedman}
\citation{Lambek:sentstruct}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {6}{\ignorespaces The Earley deductive parsing system modified to generate derivation trees.}}{14}}
\newlabel{fig:earley-mod}{{6}{14}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {4.2}Combinatory Categorial Grammars}{14}}
\newlabel{sec:ccg}{{4.2}{14}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {7}{\ignorespaces An example CCG lexicon.}}{15}}
\newlabel{fig:ccgtoy}{{7}{15}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {8}{\ignorespaces The CCG deductive parsing system.}}{16}}
\newlabel{fig:ccg}{{8}{16}}
\newlabel{eg-sent-ccg}{{2}{16}}
\citation{jlt75,j83}
\citation{schabes-ci94,ss92a}
\citation{kj85}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {9}{\ignorespaces An example tree-adjoining grammar consisting of one initial tree (a), and one auxiliary tree (b). These trees can be used to form the derived tree (c) for the sentence ``Trip rumbas nimbly.'' (In an actual English grammar, the tree depicted in (a) would not be an elementary tree, but itself derived from two trees, one for each lexical item, by a substitution operation.)}}{17}}
\newlabel{fig:example}{{9}{17}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {4.3}Tree-Adjoining Grammars and Related Formalisms}{17}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {10}{\ignorespaces The operation of adjunction. The auxiliary tree is spliced into the initial tree to yield the derived tree at right.}}{18}}
\newlabel{fig:adjoin}{{10}{18}}
\citation{v87}
\citation{schabes-ci94}
\citation{vw93}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {11}{\ignorespaces Examples of dot movement in the CYK tree traversal implicit in the TAG parsing algorithm.}}{21}}
\newlabel{fig:trav}{{11}{21}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {12}{\ignorespaces The CYK deductive parsing system for tree-adjoining grammars.}}{22}}
\newlabel{fig:tag-parse}{{12}{22}}
\citation{schabes-ci94}
\citation{xtag92}
\citation{ss92a}
\citation{schabes93,sw-TR-94-13}
\citation{sw-TR-94-13}
\citation{Lambek:sentstruct,Moortgat:categorial}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {4.4}Inadequacy for Sequent Calculi}{23}}
\citation{Pareschi+Miller:ICLP90,Hodas:gaps}
\citation{Bancilhon+Ramakrishnan:amateur,Ramakrishan:templates}
\citation{Pentus93}
\citation{kay-chart-parsing}
\citation{ka65,y67}
\citation{e70}
\newlabel{right-slash}{{3}{24}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {5}CONTROL AND IMPLEMENTATION}{24}}
\newlabel{sec:control}{{5}{24}}
\newlabel{sec:procedure}{{5}{25}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Soundness}{25}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Completeness}{26}}
\newlabel{eqn:rule-app}{{4}{26}}
\citation{Lassez+al:revisited}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.1}Eliminating Redundancy}{27}}
\newlabel{sec:redundancy}{{5.1}{27}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Redundancy in the chart.}{27}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Definition of ``redundant item''.}{27}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Redundancy in the agenda.}{27}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Triggering the generation of new immediate consequences.}{27}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.2}Providing Efficient Access}{28}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Indexing for redundancy checking.}{28}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Indexing for antecedent lookup.}{28}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Variable renaming.}{28}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.3}Prolog Implementation of Deductive Parsing}{28}}
\newlabel{sec:impl}{{5.3}{28}}
\@writefile{toc}{\string\contentsline\space {subsubsection}{\string\numberline\space {5.3.1}Implementation of Agenda and Chart}{29}}
\@writefile{toc}{\string\contentsline\space {subsubsection}{\string\numberline\space {5.3.2}Implementation of the Deduction Engine}{30}}
\@writefile{toc}{\string\contentsline\space {subsubsection}{\string\numberline\space {5.3.3}Implementation of Other Aspects}{31}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.4}Alternative Implementations}{31}}
\citation{Ramakrishnan+al:coral}
\citation{cle}
\@writefile{toc}{\string\contentsline\space {paragraph}{Separate agenda and chart in database.}{32}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Passing agenda as argument.}{32}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Efficient bottom-up interpretation.}{32}}
\newlabel{sec:imp-offline}{{5.4}{32}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Construction of derivations.}{32}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Finer control of execution order}{33}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {6}CONCLUSION}{34}}
\bibstyle{plain}
\bibdata{infer}
\bibcite{ades-steedman}{1}
\bibcite{cle}{2}
\bibcite{Bancilhon+Ramakrishnan:amateur}{3}
\bibcite{Billot+Lang:shared}{4}
\bibcite{Bresnan+Kaplan:lfg}{5}
\bibcite{Carpenter:logic}{6}
\bibcite{Colmerauer:mgs}{7}
\bibcite{e70}{8}
\bibcite{Hodas:gaps}{9}
\bibcite{j83}{10}
\bibcite{jlt75}{11}
\bibcite{ka65}{12}
\bibcite{kay-chart-parsing}{13}
\bibcite{kj85}{14}
\bibcite{Lambek:sentstruct}{15}
\bibcite{Lang:74}{16}
\bibcite{Lassez+al:revisited}{17}
\bibcite{Moortgat:categorial}{18}
\bibcite{Naughton+Ramakrishnan:bottom-up}{19}
\bibcite{Pareschi+Miller:ICLP90}{20}
\bibcite{xtag92}{21}
\bibcite{Pentus93}{22}
\bibcite{Pereira+Warren:DCGs}{23}
\bibcite{Pereira+Warren:ED}{24}
\bibcite{Ramakrishan:templates}{25}
\bibcite{Ramakrishnan+al:coral}{26}
\bibcite{Rounds+Manaster-Ramer:fg}{27}
\bibcite{Sato+Tamaki:patterns}{28}
\bibcite{schabes-ci94}{29}
\bibcite{ss92a}{30}
\bibcite{schabes93}{31}
\bibcite{sw-TR-94-13}{32}
\bibcite{Shieber:criteria}{33}
\bibcite{Shieber:restriction}{34}
\bibcite{Shieber:inference}{35}
\bibcite{v87}{36}
\bibcite{vw93}{37}
\bibcite{y67}{38}