Show simple item record

Palindromi u konačnim i beskonačnim rečima

dc.contributor.advisorPetrović, Vojislav
dc.contributor.otherMarković, Petar
dc.contributor.otherDolinka, Igor
dc.contributor.otherBošnjak, Ivica
dc.contributor.otherDoroslovački, Rade
dc.creatorBašić, Bojan
dc.date.accessioned2021-02-25T14:52:40Z
dc.date.available2021-02-25T14:52:40Z
dc.date.issued2012-09-30
dc.identifier.urihttps://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija157243216140930.pdf?controlNumber=(BISIS)81611&fileName=157243216140930.pdf&id=14073&source=NaRDuS&language=srsr
dc.identifier.urihttps://www.cris.uns.ac.rs/record.jsf?recordId=81611&source=NaRDuS&language=srsr
dc.identifier.urihttps://www.cris.uns.ac.rs/DownloadFileServlet/IzvestajKomisije160129161301483.pdf?controlNumber=(BISIS)81611&fileName=160129161301483.pdf&id=16835&source=NaRDuS&language=srsr
dc.identifier.uri/DownloadFileServlet/IzvestajKomisije160129161301483.pdf?controlNumber=(BISIS)81611&fileName=160129161301483.pdf&id=16835
dc.identifier.urihttps://nardus.mpn.gov.rs/handle/123456789/17888
dc.description.abstractIn the thesis we are concerned with actual problems on palindromic subwords and palindromic factors of finite and infinite words. The main course of the research are the ways of determining which of two given words is “more palindromic” than the other one, that is, defining a measure for the degree of “palindromicity” of a word. Particularly, we pay attention to two actual approaches: the so-called MP-ratio and the so-called palindromic defect, and answer several open questions about them. Namely, concerning the MP-ratio, a few plausible-looking question have been asked in the literature, which would have, if answered positively, made computations of MP-ratios significantly simpler. We add one more related question to these ones, and then show that, rather unexpectedly, all these questions have negative answer. Concerning the palindromic defect, the main result of this work is a construction of an infinite class of infinite words that have several properties that were sought after in some recent works in this area. Among the most interesting facts is that that all these words are aperiodic words of a finite positive defect, having the set of factors closed under reversal---in some recent works, the construction of even a single word having these properties turned out to be quite hard. Using these words, which we are calling highly potential words, we check the validity of several open  conjectures, and for several of them we find out that they are false.en
dc.description.abstractU tezi razmatramo aktuelne probleme u vezi s palindromskim podrečima i palindromskim faktorima konačnih i beskonačnih reči. Glavni pravac istraživanja jesu kriterijumi za određivanje koja od dve date reči je „palindromičnija“ od druge, tj. određivanje stepena „palindromičnosti“ date reči. Akcenat stavljamo na dva aktuelna pristupa: tzv. MP-razmeru i tzv. palindromski defekt, i odgovaramo na više otvorenih pitanja u vezi s njima. Naime, u vezi sa MP-razmerom u literaturi je postavljeno više pitanja, intuitivno uverljivih, koja bi, u slučaju pozitivnog razrešenja, znatno pojednostavila izračunavanje MP-razmere. Ovim pitanjima dodajemo još jedno srodno, a zatim pokazujemo da, prilično neočekivano, sva ova pitanja imaju negativan odgovor. U vezi s palindromskim defektom, glavni rezultat rada je konstrukcija beskonačne klase beskonačnih reči koje imaju više osobina za kojima je iskazana potreba u skorašnjim radovima iz ove oblasti. Među najzanimljivije spada činjenica da su sve aperiodične reči konačnog pozitivnog defekta, i da im je skup faktora zatvoren za preokretanje – u nekim skorašnjim radovima konstrukcija makar jedne reči s ovim osobinama pokazala se kao prilično teška. Pomoću ovih reči, koje nazivamo visokopotencijalne reči, ispitujemo validnost više otvorenih hipoteza, i za više njih ustanovljavamo da nisu validne.sr
dc.languageen
dc.publisherУниверзитет у Новом Саду, Природно-математички факултетsr
dc.rightsopenAccessen
dc.rights.urihttps://creativecommons.org/licenses/by-nc/4.0/
dc.sourceУниверзитет у Новом Садуsr
dc.subjectpalindromeen
dc.subjectpalindromsr
dc.subjectsubworden
dc.subjectfactoren
dc.subjectfactor complexityen
dc.subjectpalindromic complexityen
dc.subjectdefecten
dc.subjectpodrečsr
dc.subjectfaktor,faktorska složenost,palindromska složenostsr
dc.subjectdefeksr
dc.titlePalindromes in finite and infinite wordsen
dc.title.alternativePalindromi u konačnim i beskonačnim rečimasr
dc.typedoctoralThesisen
dc.rights.licenseBY-NC
dcterms.abstractПетровић, Војислав; Марковић, Петар; Бошњак, Ивица; Долинка, Игор; Дорословачки, Раде; Башић, Бојан;
dc.identifier.fulltexthttps://nardus.mpn.gov.rs/bitstream/id/68486/IzvestajKomisije.pdf
dc.identifier.fulltexthttps://nardus.mpn.gov.rs/bitstream/id/68485/Disertacija.pdf
dc.identifier.rcubhttps://hdl.handle.net/21.15107/rcub_nardus_17888


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record