کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435271 | 689889 | 2016 | 16 صفحه PDF | دانلود رایگان |
A finite deterministic automaton A=(Q,Σ,δ)A=(Q,Σ,δ) is k -compressible if there is a word w∈Σ+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 AA. It is known that, for any alphabet Σ and any k≥2k≥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≥3n≥3 is co-NP-complete. The computational complexity of recognizing k -collapsing words with k≥3k≥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=3k=3 and n=2n=2.
Journal: Theoretical Computer Science - Volume 629, 23 May 2016, Pages 64–79