A finite deterministic automaton is called n-compressible is there exists a word w on the alphabet of the automaton such that under the natural action of w the image of the automaton state set is reduced by at least n states and w is called an n-compressing word for the automaton. A word on a finite alphabet A that is n-compressing for all n-compressible automata on the alphabet A is called n-collapsing. In this paper we prove that the problem of recognizing n-collapsing words is generally co-NP-complete, while restricted to 2-collapsing words over 2-element alphabet it belongs to P. This is connected with introducing a new approach to collapsing words, which is shown to be much more effective in solving various problems in the area. It leads to interesting connections with combinatorial problems concerning solving systems of permutation conditions on one hand, and coloring trees with distinguished nodes on the other hand.

Collapsing words, permutation conditions and coherent colorings of trees

CHERUBINI, ALESSANDRA;
2009-01-01

Abstract

A finite deterministic automaton is called n-compressible is there exists a word w on the alphabet of the automaton such that under the natural action of w the image of the automaton state set is reduced by at least n states and w is called an n-compressing word for the automaton. A word on a finite alphabet A that is n-compressing for all n-compressible automata on the alphabet A is called n-collapsing. In this paper we prove that the problem of recognizing n-collapsing words is generally co-NP-complete, while restricted to 2-collapsing words over 2-element alphabet it belongs to P. This is connected with introducing a new approach to collapsing words, which is shown to be much more effective in solving various problems in the area. It leads to interesting connections with combinatorial problems concerning solving systems of permutation conditions on one hand, and coloring trees with distinguished nodes on the other hand.
deterministic finite automaton; n-collapsing word; permutation; coloring; NP-complete problem
File in questo prodotto:
File Dimensione Formato  
collapsing_words.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 964.26 kB
Formato Adobe PDF
964.26 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/548984
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact