@inproceedings{kipps-1989-analysis,
    title = "Analysis of Tomita{'}s Algorithm for General Context-Free Parsing",
    author = "Kipps, James R.",
    editor = "Tomita, Masaru",
    booktitle = "Proceedings of the First International Workshop on Parsing Technologies",
    month = aug,
    year = "1989",
    address = "Pittsburgh, Pennsylvania, USA",
    publisher = "Carnegy Mellon University",
    url = "https://preview.aclanthology.org/fix-sig-urls/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."
}