Codice | QDD 35 |
Titolo | Collapsing words |
Data | 2008-07-08 |
Autore/i | Cherubini, A.; Kisielewicz, A. |
Link | Download full text | Pubblicato | TCS |
Abstract | Given a word $w$ over a finite alphabet $ Sigma$ and a finite
deterministic automaton $ A = < Q, Sigma, delta >$, the inequality
$| delta(Q,w)| leq |Q|-n$ means that under the natural action of
the word $w$ the image of the state set $Q$ is reduced by at least
$n$ states. A word $w$ is $n$-collapsing if this inequality holds
for any deterministic finite automaton that satisfies such an
inequality for at least one word. 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. |
|