TY - JOUR

T1 - The size of subsequence automaton

AU - Troníček, Zdeněk

AU - Shinohara, Ayumi

PY - 2005/9/5

Y1 - 2005/9/5

N2 - 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.

AB - 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.

KW - Directed acyclic subsequence graph

KW - Searching subsequences

KW - Subsequence automaton

UR - http://www.scopus.com/inward/record.url?scp=23844557169&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23844557169&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2005.03.027

DO - 10.1016/j.tcs.2005.03.027

M3 - Article

AN - SCOPUS:23844557169

SN - 0304-3975

VL - 341

SP - 379

EP - 384

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -