A1 Refereed original research article in a scientific journal
Separating the Words of a Language by Counting Factors
Authors: Saarela Aleksi
Publisher: IOS PRESS
Publication year: 2021
Journal: Fundamenta Informaticae
Journal name in source: FUNDAMENTA INFORMATICAE
Journal acronym: FUND INFORM
Volume: 180
Issue: 4
First page : 375
Last page: 393
Number of pages: 19
ISSN: 0169-2968
DOI: https://doi.org/10.3233/FI-2021-2047
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/66682260
Abstract
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.
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.
Keywords:
infinite word, k-abelian equivalence
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal