String algorithms and their implementation, intelligent tutors

点击翻译按钮获取中文摘要

(1) Suffix data structures and related algorithms. The focus of the research is "relaxed" versions of suffix trees and arrays (i.e. without regards to lexicograhic ordering); their computation in linear time with hight memory efficiency, their transformation to "regular" suffix trees and arrays, their use for applications. The main objective is a fast linear non-recursive memory efficient algorithm for computing suffix trees and arrays. The research will explore the following path to such an algorithm: first compute a "relaxed" version of the data structure, then transform it to the "regular" structure. (2) The periodicity in strings. The investigation of mathematical and combinatorial properties of the function r(n) - the maximun number of runs (maximal non-extendible repetitions) over all strings of length n. The main objectives are: to prove that asymptoticaly r(n)