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 ≥ 3 is co-NP-complete. A natural question in this context, whether recognizing 3-collapsing words over a 2-element alphabet is easy or hard, has remained open. In this paper we provide results on 3-compressible binary automata, which allow to prove that that the latter problem is co-NP-complete

Binary 3-compressible automata

CHERUBINI, ALESSANDRA;
2014-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 ≥ 3 is co-NP-complete. A natural question in this context, whether recognizing 3-collapsing words over a 2-element alphabet is easy or hard, has remained open. In this paper we provide results on 3-compressible binary automata, which allow to prove that that the latter problem is co-NP-complete
Proceedings of the 15th Italian Conference on Theoretical Computer Science
.k-compressible automata, k-collapsing words, finite automata
File in questo prodotto:
File Dimensione Formato  
long8.pdf

Accesso riservato

Descrizione: Articolo principale
: Publisher’s version
Dimensione 586.85 kB
Formato Adobe PDF
586.85 kB Adobe PDF   Visualizza/Apri

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/11311/974426
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact