Conference of Young Programmers and Mathematicians [antikvár]

CÉf THE SU3SEQÜETTCE COMPLEJCITY C? 7XRDS by László Hunvadvari and Antal Iványi /Budapest, Eötvös Loránd University/ Introduction The us /or me uai com.Dl exit v measures of secuences are based on ' **- o Ü1I..C mory/ nee ded v « for generating, recognizing them, r y\ 11 * t nx s paper a new tvt) v -¦ e of corr.plexity measures, the d-subse qu- o v, r> o >_ lA W ccr.plexity is s tudi ed. Tv- p * _ subsequen ce complexity alsó is intended to exp •hl/ • res o ¦ M a * • v f v era«* e quantitv x of í v) t* c i ; i"-* o 1 y. + V^ p o ff " 1" o "v* ¦•> ixv-r w c Th í ^ ^ l . JU o ccncep •f p^rpr cp.tő V V^ w » VA VMk w '.-cnown and studied earlier ccmplex itv w d c. c! • - W Vi üres as subword v w 4. . ^ lexity /case d-1/ [1,2,3,4,5,7,9] C3 d subs eouence nomplexity / case d*oo/ [ő]o The backrr >uná of the new corr.plexity measure lies in biology* Somé natural sequences, as amino-acid secuences in proteins ~r rucleotid se:uences in DNS-moleculas have winding struct'ire [l ? íH and sorr.e bende can be cut fcrming new and, of c:urse, shorter sequences. The parameter d is the bgund for the length of bends, which can be cut, Dr, with other words, d is the maxi mai penr.is?íble distsnce between two remeining elemer.ts :f two sequence. 7/e deíine four cor.plexity ir.easures and investigate their properties as bound?, monoton!ty for the ccneatenation of a word and a letter, additivity for the ecncatenation #f two words, relatíve corr.plexity of concatenations, In most cases we can prove tight bounds of the investigated complexity vs~ lues as functions cf the basic peremeters /length of wcrds, size of alphabet/o It is assumed that the reader is fangiliar with the basic concepts and notations cf formai language theory. In the paper all terms and symbols are used as in Salomaa1s book QQ/inless indicated otherwise/, !<. Complexity ir.easures of wirds Let n /2^n^oo/ be an integer, , x2, • •«, be a