National Repository of Dissertations in Serbia
    • English
    • Српски
    • Српски (Serbia)
  • English 
    • English
    • Serbian (Cyrilic)
    • Serbian (Latin)
  • Login
View Item 
  •   NaRDuS home
  • Универзитет у Новом Саду
  • Природно-математички факултет
  • View Item
  •   NaRDuS home
  • Универзитет у Новом Саду
  • Природно-математички факултет
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

On some reversal-invariant complexity measures of multiary words

O nekim reverznoinvarijantnim merama složenosti visearnih reči

Thumbnail
2020
Disertacija.pdf (1.153Mb)
IzvestajKomisije.pdf (256.6Kb)
Author
Ago-Balog, Kristina
Mentor
Bašić, Bojan
Committee members
Bošnjak, Ivica
Bašić, Bojan
Radovanović, Marko
Šobot, Boris
Metadata
Show full item record
Abstract
We focus on two complexity measures of words that are invariant under the operation of reversal of a word: the palindromic defect and the MP-ratio.The palindromic defect of a given word w is dened by jwj + 1   jPal(w)j, where jPal(w)j denotes the number of palindromic factors of w. We study innite words, to which this de  nition can be naturally extended. There are many results in the literature about the so- called rich words (words  of defect 0), while words of nite positive defect have been studied signicantly less; for some time (until recently) it was not known whether there even exist such words that additionally are aperiodic and have their set of factors closed under reversal. Among the rst examples that appeared were the so-called highly potential words. In this  thesis we present a much more general construction,which gives a wider class of words, named generalized highly potential words, and analyze their signicance within the frames of combinatorics on words.The MP-ratio of... a given n-ary  word w is dened as the quotient jrwsj jwj ,where r and s are words such that the word rws is minimal- palindromic and that the length jrj + jsj is minimal possible; here, an n-ary word is called minimal-palindromic if it does not contain palindromic subwords of length greater than jwj n . In the binary case, it was proved that the MP-ratio is well-dened and that it is bounded from above by 4, which is the best possible upper bound. The question of well- denedness of the MP-ratio for larger alphabets was left open. In this thesis we solve that  question in the ternary case: we show that the MP-ratio is indeed well-dened in the ternary case, that it is bounded from above by the constant 6 and that this is the best possible upper bound.

Izucavamo dve mere slozenosti reci koje su invarijantne u odnosu na operaciju preokretanja reci: palindromski defekt i MP-razmeru date reci.Palindromski defekt reci w denise se kao jwj + 1   jPal(w)j, gde jPal(w)j predstavlja broj palindromskih faktora reci w. Mi izucavamo beskonacne reci, na koje se ova denicija moze prirodno prosiriti. Postoje mnogobrojni rezultati u vezi sa tzv. bogatim recima (reci cije je defekt 0), dok se o recima sa konacnim pozitivnim defektom relativno malo zna; tokom jednog perioda (donedavno) nije bilo poznato ni da li uopste postoje takve reci koje su,dodatno, aperiodi cne i imaju skup faktora zatvoren za preokretanje. Medu prvim primerima koji su se pojavili u literaturi su bile tzv. visokopotencijalne reci. U disertaciji cemo predstaviti znatno opstiju konstrukciju, kojom se dobija znacajno sira klasa reci, nazvanih uop stene visokopotencijalne reci, i analiziracemo njihov znacaj u okvirima kombinatorike na recima.MP-razmera date n-arne reci w denise se k...ao kolicnik jrwsj jwj , gde su r i s takve da je rec rws minimalno-palindromicna, i duzina jrj + jsj je najmanja moguca; ovde, za n-arnu rec kazemo da je minimalno-palindromicna ako ne sadrzi palindromsku podrec duzine vece od  jwj n  . U binarnom slucaju dokazano je da je MP-razmera dobro  denisana i da je ogranicena odozgo konstantom 4, sto je i najbolja moguca granica. Dobra denisanost MP-razmere za vece alfabete je ostavljena kao otvoren problem. U ovoj tezi resavamo taj problem u ternarnom slucaju: pokazacemo da MP- razmera jeste dobro de-nisana u ternarnom slucaju, da je ogranicena odozgo sa 6, i da se ta granica ne moze poboljsati.  

Faculty:
University of Novi Sad, Faculty of Science
Date:
11-09-2020
Projects:
  • Algebraic, logical and combinatorial methods with applications in theoretical computer science (RS-174018)
Keywords:
combinatorics on words, palindrome, factor, subword, palindromic defect, MP-ratio / kombinatorika na rečima, palindrom, faktor, podreč, palindromski defekt, MP-razmera
[ Google Scholar ]
URI
https://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija159074433930412.pdf?controlNumber=(BISIS)114649&fileName=159074433930412.pdf&id=15522&source=NaRDuS&language=sr
https://www.cris.uns.ac.rs/record.jsf?recordId=114649&source=NaRDuS&language=sr
https://www.cris.uns.ac.rs/DownloadFileServlet/IzvestajKomisije159074435218596.pdf?controlNumber=(BISIS)114649&fileName=159074435218596.pdf&id=15523&source=NaRDuS&language=sr
/DownloadFileServlet/IzvestajKomisije159074435218596.pdf?controlNumber=(BISIS)114649&fileName=159074435218596.pdf&id=15523
https://nardus.mpn.gov.rs/handle/123456789/17895

DSpace software copyright © 2002-2015  DuraSpace
About NaRDus | Contact us

OpenAIRERCUBRODOSTEMPUS
 

 

Browse

All of DSpaceUniversities & FacultiesAuthorsMentorCommittee membersSubjectsThis CollectionAuthorsMentorCommittee membersSubjects

DSpace software copyright © 2002-2015  DuraSpace
About NaRDus | Contact us

OpenAIRERCUBRODOSTEMPUS