Log Space Recognition and Translation of Parenthesis Languages
Nancy Ann Lynch · Journal of the ACM · 1977
It ~S shown how to determine membership in any parenthesis context-free language in log space As an apphcatton, the evaluation of Boolean sentences ~s shown to be log space computable Log space translatton of parenthesis languages ~s slmdarly shown to be possible, thus log space translators among various representations of Boolean formulas may be constructed