On the Complexity of Simon Automata over the Dyck Language
Flavio D’Alessandro · IRIS Research product catalog (Sapienza University of Rome) · 2003
In this paper the following problem is studied Let $\bar\Sigma=\Sigma\cup\bar\Sigma$ be a finite alphabet where $\Sigma$ and $\bar\Sigma$ are disjoint and equipotent sets. Let $L$ be a rational language over $\bar\Sigma$ and let $S_L$ 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 $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 $\Sigma$ is the unary alphabet. This result partially solves an open question raised in [4].