Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in the expression. For example, the program should print true with begin-end pair of symbols indices for exp = “[()]{}{()()}” and false for exp = “[(])”.

The naive solution with a stack has O(n) time-complexity and O(n) space-complexity. Can we solve this problem in O(log(n)) space-complexity? In other words, can we parse Dyck languages in logarithmic space?

  • 2
    $\begingroup$ LOGCFL contains NL, so my guess is that if your input tape is read-only, you can't do this in logarithmic space. $\endgroup$ Commented Aug 29, 2016 at 15:21
  • $\begingroup$ Do the different types of parentheses have to nest properly, which would give a Dyck language, or can they appear independently of each other, which would make the language non-CFL? $\endgroup$
    – Raphael
    Commented Aug 29, 2016 at 15:38
  • 1
    $\begingroup$ Thanks. So your question is: Can we parse Dyck-languages in logarithmic space? (You may want to Google using these terms.) $\endgroup$
    – Raphael
    Commented Aug 29, 2016 at 17:06
  • $\begingroup$ Have you seen this article? $\endgroup$
    – Evil
    Commented Aug 29, 2016 at 21:44
  • $\begingroup$ Do you require the time-complexity of the logarithmic space algorithm to still be linear? Or are you looking for a time-space tradeoff? $\endgroup$
    – rici
    Commented Aug 30, 2016 at 0:45

1 Answer 1


The Dyck language on any fixed number of symbols can be recognised by a marking automaton, which is a two-way finite automaton that can mark a fixed number of input tape squares. The automaton simply uses a different mark for each type of parenthesis. Since a marking automaton is easily implemented by a Turing machine with a fixed number of logarithmic-sized regions of the worktape forming pointers into the input, Dyck languages can be parsed in logspace.

  • R. W. Ritchie and F. N. Springsteel, Language Recognition by Marking Automata, Information and Control 20, 313–330, 1972. doi:10.1016/S0019-9958(72)90205-7

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.