The rewrite relation with parameters m and n and with the possible lengthlimit = k or :::; k we denote by w~, =kW~· or ::;kw~ respectively. Theidempotency languages generated from a starting word w by the respectiveoperations are wD<l::', w=kD<l::' and W<;kD<l::'.Also other special cases of idempotency languages besides duplication havecome up in different contexts. The investigations of Ito et al. about insertionand deletion, Le., operations that are also observed in DNA molecules, haveestablished that w5 and w~ both preserve regularity.Our investigations about idempotency relations and languages start out fromthe case of a uniform length bound. For these relations =kW~ the conditionsfor confluence are characterized completely. Also the question of regularity is-k n answered for aH the languages w- D<lm . They are nearly always regular. Onlythe languages wD<lo for n > 1 are more complicated and belong to the class ofcontext-free languages.For a generallength bound, i.e."for the relations :"::kW~, confluence doesnot hold so frequently. This complicatedness of the relations results also inmore complicated languages, which are often non-regular, as for example thelanguages W<;kD<l::' for aH bounds k 2 4. For k :::; 2 they are regular. The case ofk :::; 3, though, remains open. We show, however, that none of these languagesever exceeds the complexity of being context-free.Without any length bound, idempotency relations have a very complicatedstructure. Over alphabets of one or two letters we still characterize the conditionsfor confluence. Over three or more letters, in contrast, only a few casesare solved. We determine the combinations of parameters that result in theregularity of wD<l::', when the alphabet of w contains only two letters. Only thecase of 2 :::; m < n remains open.In a second chapter sorne more involved questions are solved for the specialcase of duplication. First we shed sorne light on the reasons why it is so difficultto determine the context-freeness ofduplication languages. We show that theyfulfiH aH pumping properties and that they are very dense. Therefore aH thestandard tools to prove non-context-freness do not apply here.The concept of root in Formal Language ·Theory is frequently used to describethe reduction of a word to another one, which is in sorne sense elementary.For example, there are primitive roots, periodicity roots, etc. Elementaryin connection with duplication are square-free words, Le., words that do notcontain any repetition. Thus we define the duplication root of w to consist ofaH the square-free words, from which w can be reached via the relation w~.Besides sorne general observations we prove the decidability of the question,whether the duplication root of a language is finite.Then we devise acode, which is robust under duplication of its code words.This would keep the result of a computation from being destroyed by duplications in the code words. We determine the exact conditions, under whichinfinite such codes exist: over an alphabet of two letters they exist for a lengthbound of 2, over three letters already for a length bound of 1.Also we apply duplication to entire languages rather than to single words;then it is interesting to determine, whether regular and context-free languagesare closed under this operation. We show that the regular languages are closedunder uniformly bounded duplication, while they are not closed under duplicationwith a generallength bound. The context-free languages are closed underboth operations.The thesis concludes with a list of open problems related with the thesis'topics.
| Identifer | oai:union.ndltd.org:TDX_URV/oai:www.tdx.cat:10803/8793 |
| Date | 22 November 2006 |
| Creators | Leupold, Klaus-Peter |
| Contributors | Karhumäki, Juhani, Mitrana, Victor, Universitat Rovira i Virgili. Departament de Filologies Romàniques |
| Publisher | Universitat Rovira i Virgili |
| Source Sets | Universitat Rovira i Virgili |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, ADVERTIMENT. La consulta d'aquesta tesi queda condicionada a l'acceptació de les següents condicions d'ús. La difusió d'aquesta tesi per mitjà del servei TDX ha estat autoritzada pels titulars dels drets de propietat intel·lectual únicament per a usos privats emmarcats en activitats d'investigació i docència. No s'autoritza la seva reproducció amb finalitats de lucre ni la seva difusió i posada a disposició des d'un lloc aliè al servei TDX. No s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant al resum de presentació de la tesi com als seus continguts. En la utilització o cita de parts de la tesi és obligat indicar el nom de la persona autora. |
Page generated in 0.0018 seconds