5
$\begingroup$

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?

$\endgroup$
  • 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$ – Yuval Filmus Aug 29 '16 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 Aug 29 '16 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 Aug 29 '16 at 17:06
  • $\begingroup$ Have you seen this article? $\endgroup$ – Evil Aug 29 '16 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 Aug 30 '16 at 0:45
6
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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