@inproceedings{kipps-1989-analysis,
title = "Analysis of Tomita{'}s Algorithm for General Context-Free Parsing",
author = "Kipps, James R.",
booktitle = "Proceedings of the First International Workshop on Parsing Technologies",
month = aug,
year = "1989",
address = "Pittsburgh, Pennsylvania, USA",
publisher = "Carnegy Mellon University",
url = "https://www.aclweb.org/anthology/W89-0220",
pages = "193--202",
abstract = "A variation on Tomita{'}s algorithm is analyzed in regards to its time and space complexity. It is shown to have a general time bound of $0(n^{\tilde{\rho}+1})$, where $n$ is the length of the input string and $\rho$ is the length of the longest production. A modified algorithm is presented in which the time bound is reduced to $0(n^3)$. The space complexity of Tomita{'}s algorithm is shown to be proportional to $n^2$ in the worst case and is changed by at most a constant factor with the modification. Empirical results are used to illustrate the trade off between time and space on a simple example. A discussion of two subclasses of context-free grammars that can be recognized in $0(n^2)$ and $O(n)$ is also included.",
}