Word Border Algorithm and Its Application in Determining the Smallest Conjugate of a Word

Word comprises the core topic of combinatorics on words. Word is a finite or infinite sequence of symbols taken from a finite set called alphabet. Combinatorics on words has different applications in various sciences including logic, algebra, biology, computer science, math and game, numbers theory, computation theory and another branches of mathematics. In this scope, various properties and algorithms have been proposed based on words. Among the proposed algorithms, one may refer to word border algorithm which studies interference or overlap of a word by itself and the smallest conjugate of a word between the terms of the class of the conjugation of that word in the alphabetic order. In the present paper, two algorithms are investigated, namely polynomial- and linear-time word border algorithms, with their applications in determining the smallest conjugate of a word being further studied.We will also studied the smallest conjugate algorithm in both linear and nonlinear times.

کلیدواژه ها:

word ، combinatorics on words ، word border ، conjugate of word