Check for balanced parentheses in an expression in log-space

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?

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

StackExchange Computer Science Q#63008, answer score: 7