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)].

On the complexity of Simon automata over the Dyck language / D'Alessandro, Flavio. - In: JOURNAL OF AUTOMATA, LANGUAGES AND COMBINATORICS. - ISSN 1430-189X. - STAMPA. - 8:(2003), pp. 465-476.

On the complexity of Simon automata over the Dyck language

D'ALESSANDRO, Flavio
2003

Abstract

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)].
2003
01 Pubblicazione su rivista::01a Articolo in rivista
On the complexity of Simon automata over the Dyck language / D'Alessandro, Flavio. - In: JOURNAL OF AUTOMATA, LANGUAGES AND COMBINATORICS. - ISSN 1430-189X. - STAMPA. - 8:(2003), pp. 465-476.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/122655
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact