On the Complexity of Simon Automata over the Dyck Language

In this paper the following problem is studied. Let Σ = Σ ∪ Σ be a finite alphabet where Σ and Σ, are disjoint and equipotent sets. Let L be a rational language over Σ and let SL be the Simon distance automaton of L. Let C be the square matrix with entries in the extended set of natural numbers given by the formula: for every pair (p, q) of states of SL, Cpq is the minimum weight of a computation in SL from p to q labelled by a Dyck word if such a computation exists, otherwise it is ∞. We exhibit a polynomial time algorithm which allows us to compute the matrix C in the case Σ is the unary alphabet. This result partially solves an open question raised in [4].