Word Border Algorithm and Its Application in Determining the Smallest Conjugate of a Word
Publish place: 11th International Conference on Information Technology, Computer and Telecommunications
Publish Year: 1399
نوع سند: مقاله کنفرانسی
زبان: English
View: 334
This Paper With 8 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ITCT11_003
تاریخ نمایه سازی: 18 اردیبهشت 1400
Abstract:
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.
Keywords:
Authors
Elham Asadi
Department of computer Shahr-e Babak Branch,Islamic Azad University Shahr-e Babak, Iran