Separating the Words of a Language by Counting Factors



: Saarela Aleksi

Publisher: IOS PRESS

: 2021

: Fundamenta Informaticae

: FUNDAMENTA INFORMATICAE

: FUND INFORM

: 180

: 4

: 375

: 393

: 19

: 0169-2968

DOI: https://doi.org/10.3233/FI-2021-2047

: https://research.utu.fi/converis/portal/detail/Publication/66682260


For a given language L, we study the languages X such that for all distinct words u; v is an element of L, there exists a word x is an element of X that appears 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.

Last updated on 2024-26-11 at 21:38