The size of subsequence automaton

Zdeněk Troníček, Ayumi Shinohara

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)379-384
Number of pages6
JournalTheoretical Computer Science
Issue number1-3
Publication statusPublished - 2005 Sept 5


  • Directed acyclic subsequence graph
  • Searching subsequences
  • Subsequence automaton


Dive into the research topics of 'The size of subsequence automaton'. Together they form a unique fingerprint.

Cite this