Separating many words by counting occurrences of factors

Final draft
ssf.pdf - 310.96 KB
Lataukset161

Verkkojulkaisu

Tiivistelmä

For a given language L, we study the languages X such that for all distinct words   u,v∈L , there exists a word   x∈X  appearing a different number of times as a factor in u and in v. In particular, we are interested in the following question: For which languages L does there exist a finite language X satisfying the above condition? We answer this question for all regular languages and for all sets of factors of infinite words.

Sarja

Theoretical Computer Science and General Issues

item.page.okmtext