Paper Info
Title
Linear-time suffix parsing for deterministic languages
Abstract
We present a linear-time algorithm to decide for any fixed deterministic context-free language L and input string w whether wis 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 pocess incorrect input in linear time.
Year
DOI
Venue
1996
10.1145/233551.233555
J. ACM
Keywords
DocType
Volume
Linear-time suffix,pocess incorrect input,fixed deterministic context-free language,decision procedure,deterministic language,syntactic structure,linear-time algorithm,linear time,time complexity,input string w
Journal
43
Issue
ISSN
Citations 
3
0004-5411
7
PageRank 
References 
Authors
0.64
16
2
Name
Order
Citations
PageRank
Mark-jan Nederhof138753.30
Eberhard Bertsch26326.54