On the complexity of Simon automata over the Dyck language

In this paper the following problem is studied. Let $\tilde\Sigma=\Sigma\cup\overline\Sigma$ be a finite alphabet where $\Sigma$ and $\overline\Sigma$ are disjoint and equipotent sets. Let $L$ be a rational language over $\tilde\Sigma$ and let $S_L$ be the Simon distance automaton on $L$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 $S_L$, $C_{pq}$ is the minimum weight of a computation in $S_L$ from $p$ to $q$ labelled by a Dyck word if such a computation exists, otherwise it is $\infty$. We exhibit a polynomial time algorithm which allows us to compute the matrix $C$ in the case in which $\Sigma$ is the unary alphabet. This result partially solves an open question raised in [F. d'Alessandro and J. Sakarovitch, Theoret. Comput. Sci. 293 (2003), no. 1, 55--82; MR1957613 (2003m:20025)].