Article ID Journal Published Year Pages File Type
9657810 Theoretical Computer Science 2005 6 Pages PDF
Abstract
Given a set of strings, the subsequence automaton accepts all subsequences of these strings. We derive a lower bound for the maximum number of states of this automaton. We prove that the size of the subsequence automaton for a set of k strings of length n is Ω(nk/(k+1)kk!) for any k⩾1. It solves an open problem because only the case k⩽2 was shown before.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
The size of subsequence automaton
Authors
, ,