A finite deterministic automaton A=(Q,Σ,δ) is k-compressible if there is a word w∈Σ+ such that the image of the state set Q under the natural action of w is reduced by at least k states. In such case w is called a k-compressing word for A. It is known that, for any alphabet Σ and any k≥2, there exist words that are k-compressing for each k-compressible automaton with the input alphabet Σ. Such words are called k-collapsing. It has been proved that recognizing 2-collapsing words over a 2-element alphabet may be done in polynomial time, while recognizing 2-collapsing words over an alphabet of size n≥3 is co-NP-complete. The computational complexity of recognizing k-collapsing words with k≥3 over an n-element alphabet has remained open. In this paper we prove that this remaining problem is co-NP-complete in the simplest case with k=3 and n=2.
Recognizing 3-collapsing words over a binary alphabet
CHERUBINI, ALESSANDRA;
2016-01-01
Abstract
A finite deterministic automaton A=(Q,Σ,δ) is k-compressible if there is a word w∈Σ+ such that the image of the state set Q under the natural action of w is reduced by at least k states. In such case w is called a k-compressing word for A. It is known that, for any alphabet Σ and any k≥2, there exist words that are k-compressing for each k-compressible automaton with the input alphabet Σ. Such words are called k-collapsing. It has been proved that recognizing 2-collapsing words over a 2-element alphabet may be done in polynomial time, while recognizing 2-collapsing words over an alphabet of size n≥3 is co-NP-complete. The computational complexity of recognizing k-collapsing words with k≥3 over an n-element alphabet has remained open. In this paper we prove that this remaining problem is co-NP-complete in the simplest case with k=3 and n=2.File | Dimensione | Formato | |
---|---|---|---|
1-s2.0-S0304397515009639-main.pdf
Accesso riservato
Descrizione: Articolo principale
:
Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione
1.08 MB
Formato
Adobe PDF
|
1.08 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.