%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "nederhofb96.ltx",
%%%     date      = "9 August 1996",
%%%     time      = "15:9:31 EDT",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "20616 95 361 3164",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{NederhofB96}

\title{Linear-Time Suffix Parsing for Deterministic Languages}

\author{Mark-Jan Nederhof \and Eberhard Bertsch}

\Pages{524--554}

\Month{May}

\Year{1996}

\Volume{43}

\Number{3}

\maketitle

\begin{abstract}

We present a linear-time algorithm to decide for any fixed
deterministic context-free language~$L$ and input string~$w$ whether
$w$~is a suffix of some string in~$L$. In contrast to a previously
published technique, the decision procedure may be extended to produce
syntactic structures (parses) without an increase in time complexity.
We also show how this algorithm may be applied to process incorrect
input in linear time.

\end{abstract}

\begin{categories}

D.3.4 [\textbf{Programming Languages}]: Processors---\emph{parsing};
F.4.2 [\textbf{Mathematical Logic and Formal Languages}]: Grammars and
Other Rewriting Systems---\emph{parsing}

\end{categories}

\begin{terms}

Theory, Verification

\end{terms}

\end{document}
