Nem hagyományos modellek a formális nyelvek és automaták elméletében

Egye emi dok o i (PhD) é ekezés ézisei NEM HAGYOMÁNYOS MODELLEK A FORMÁLIS NYELVEK ÉS AUTOMATÁK ELMÉLETÉBEN Hegedüs László Téma eze ő: D . Nagy Benedek DEBRECENI EGYETEM In o ma ikai Tudományok Dok o i Iskola Deb ecen, 2016 1. Be eze és Az u óbbi néhány é izedben a számí ás udomány e üle- én egy e nagyobb igyelme szen elnek a nem hagyományos modellek izsgála ának. A ogalom igen ág, ál alában minden olyan modell ide so olha unk, amely a klasszikus szaki oda- lomban [Hopc o e al., 2006] á gyal ak ól alamilyen o má- ban el é . A elme ülő ö le ek egyik ő o ása a biológia. Ezen e üle közpon i eleme a bioinspi ál számí ás udomány (bio- inspi ed compu ing), mely az élőlényekben égbemenő biológi- ai és kémiai olyama okon alapuló mű ele ek elméle i és gya- ko la i alkalmazási lehe őségei izsgálja. Ku a ásaim so án ké bioinspi ál modellel oglalkoz am. A kö sza ak biológiai mo i ációjakén ekin he ünk a gyű- ű alakú DNS láncok a (például a mi okond iális DNS [Kiss, 2007]). Ugyanakko , az ál alam alkalmazo megközelí és ma- ema ikai eszközöke használ és a biológiai mo i áció ól üg- ge lenül oglalkozik a kö sza ak bizonyos ulajdonságai al. A kö szó, min modell nem újdonság a szaki odalomban [Cu ie and Fi zpa ick, 2002, Dieke e al., 2006, Shu , 2010], iszon az ál alam izsgál pe iódus ogalom új, még nem isme e ed- mények el edezéséhez eze e . Ku a ásaim másik á gyá képezik az egyállapo ú 50→30 1 Wa son–C ick számlálóau oma ák, melyek a DNS számí ás- udomány e üle én e ősen ku a o Wa son–C ick au oma- ák speciális ál oza ai. Az egyállapo ú 50→30Wa son– C ick számlálóau oma a egy új modell, amelynek különböző pa amé e ei jelen ősen be olyásolják ki ejezőe ejé . E edmé- nyeim leginkább az így kialakuló hie a chia el á ásán alapul- nak. 2. Célki ˝uzések és e edmények 2.1. Kö sza ak kombina o ikájá al kapcsola os célki ˝uzések A sza ak kombina o ikus ulajdonságainak elemzése egé- szen az 1900-as é ek elejé e nyúlik issza, miko is Axel Thue publikál a a négyze men es sza akkal kapcsola os mű ei [Thue, 1906, 1912]. Az első á ekin ő, össze oglaló mű e M. Lo hai e í ói álné ala publikáló ma ema ikusok csopo ja í a [Lo ha- i e, 1997]. Leg öbbjük Ma cel P. Schü zenbe ge aní ánya ol , akinek a ne éhez öbb on os é el is kapcsolódik. Va- lamennyi i emlí e mű leginkább a hagyományos (lineá is) sza ak izsgála á al oglalkozik, a kö sza akkal csak el é e alálkozha unk bennük, pedig igen é dekes megoldandó ké - dések me ülhe nek el elük kapcsola ban. Célki űzéseim és 2 e edményeim közléséhez néhány alap ogalom á ekin ése szük- séges. Fel é elezem a o mális nyel ek és au oma ák egy be- eze ő ku zuson elhangzó alap ogalmainak isme e é [Dömösi e al., 2011, Hopc o e al., 2006]. Ado Σábécé ele i ués sza ak pon osan akko egymás konjugál jai (u∼ ), ha lé eznek olyan x,y∈Σ∗sza ak, hogy u=xy és =yx. Legyen w∈Σ∗, ekko a w−ből képze kö szó ala a w◦={ ∈Σ∗| ∼w} halmaz é jük. w3 w2 w1 wn wn−1. . . 1. áb a. Kö szó Kö sza akkal kapcsola os a ciklikus el o ga ás mű ele e is, melye σ(.)− al jelölünk és, ha w=w1w2· · · wn, akko σ(w) = w2· · · wnw1. To ábbá, σ0(w) = wés, ha k∈N, akko σk(w) = σ(σk−1(w)). 3 Legyen 0=b, 1=aés e szőleges n≥2ese én n= n−1 n−2. A iszó (i∈N0)az i−edik Fibonacci szónak [Smy h, 2003], a belőle képze kö szó pedig i−edik Fibona- cci kö szónak ne ezzük. Ezen sza ak hossza pon osan a Fi- bonacci számok so oza á kö e i. Az { i}∞ i=0 eku zí so oza ha á é éké szokás ne ezni ég elen Fibonacci szónak. A kö sza ak modelljé el kapcsola ban a kö e kező elada ok megoldásá , ké dések meg álaszolásá űz em ki célul. 1. Az mondjuk, hogy a wszónak a p > 0egész szám pe i- ódusa, ha alamennyi i= 1, . .. , |w| − pese én eljesül wi=wi+p. Hogyan ál alánosí ha ó kö sza ak a a hagyo- mányos sza akon így de iniál pe iódus ogalma? 2. Lé ezik-e az így ál alánosí o pe iódus ogalom ese én ado pe iódus meglé é e ona kozó szükséges és elégsé- ges el é el? 3. Na han J. Fine és He be S. Wil pe iodici ási lemmája a hagyományos sza ak kombina o ikájának egyik leg on- osabb e edményei közé so olha ó [Lo hai e, 1997]. Ado szó ké e szőleges pe iódusa közö i kapcsola o í ja le, mégpedig az mondja ki, hogy, ha pés qis a wszó pe ió- dusa, alamin p+q−lnko(p, q)≤ |w|, akko lnko(p, q)is awpe iódusa. Lehe séges-e a Fine és Wil pe iodici ási lemma kö sza ak pe iódusai a aló ál alánosí ása? 4 4. Hagyományos sza ak zá ószele ei szokás hie a chikus ada - sze keze ekkel áb ázolni [C ochemo e and Ry e , 2002]. Hogyan használha unk hasonló ada sze keze eke kö sza- ak áb ázolásá a? 2.2. Kö sza ak kombina o ikájá al kapcsola os e edmények I isme e em, hogy az előző ejeze ben megado célki ű- zések e milyen álaszok szüle ek. A hagyományos sza akon de iniál pe iódus ogalmá elhasznál a de iniál am a gyenge pe iódus , amely a kö szó, min halmaz legalább egy elemé- nek pe iódusa. Azaz paw◦kö szó gyenge pe iódusa pon osan akko , ha lé ezik olyan ∈w◦, hogy pa pe iódusa [6]. 1. Tézis (Gyenge pe iódus lé ezésének szükséges és elégséges el é ele [1]).Legyen w∈Σ∗egy e szőleges szó. Ha paw◦ egy gyenge pe iódusa, akko lé ezik olyan |w|−phosszú x∈Σ∗ szó és `∈N0, hogy σ`(x)xaww egy ak o a. A kö e kezők is eljesülnek: I. Ha ww a almaz egy olyan xx (x∈Σ+) ak o , mely e |x|<|w|, akko p=|w|−|x|aw◦egy gyenge pe iódusa. II. Ha lé ezik olyan p > 0egész, hogy a kö e kező el é elek ennállnak: 5 •|w|=k·p+ alamely k > 0,0≤ < p ese én, alamin •lé ezik olyan phosszú ∈Σ∗szó és annak egy 0 kezdőszele e, hogy alamely 0< s < k ese én a ww szó egy ak o a σs·p( k−1 0)σ(s−1)·p( k−1 0), akko paw◦kö szó gyenge pe iódusa.  Első ézisem ehá kimondja, hogy egy ado kö szó milyen el é elek eljesülése melle endelkezik ado gyenge pe iódus- sal. 2. Tézis (Rela í p ím gyenge pe iódusok [1]).Legyenek p, q ∈ Nolyanok, hogy 2≤q < p. To ábbá, legyen w∈Σ+egy olyan szó, hogy w◦gyenge pe iódusa pés q. Jelölje ma(pmod q) é éke . Ha lnko(p, q) = 1 és wnem uná is szó, akko |w|− a eljesül a kö e kező egyenlő lenség: |w| ≤    2p−m , ha m= 1, 2p+q−m , ha m > 1.  Ez az e edmény Fine és Wil pe iodici ási lemmájának e- la í p ím gyenge pe iódusok a ona kozó ese ének ál alánosí- ása. A lemma eljes ál alánosí ása még nyi o p obléma, de 6 ez az e edmény jelen ősen hozzájá ul a megoldásához. To ábbi kapcsolódó e edménykén ekin he jük az alábbi ézis , amely ado hosszú, nem uná is kö szó különböző gyenge pe iódusa- inak maximális számá a ad pon os első ko lá o . 3. Tézis (Különböző gyenge pe iódusok maximális száma [1]). Legyen n≥3. Egy {a, b}ábécé ele i nhosszú nem uná is szó- ból képze kö szó különböző gyenge pe iódusainak száma leg el- jebb n 2+n 4+ 1, ha npá a lan, n 2+ 1, ha npá os és (nmod 3) = 2, n 2, egyébkén .  Kö sza ak áb ázolásá al kapcsola ban a a ada sze keze - ben ejlő lehe őségeke izsgál am [1,4]. A zá ószele ából (su ix ie) kiindul a be eze em a kö szóhoz a ozó a o- galmá , amelynek a gyöké ből le élelemekbe eze ő ú jain a kö szó egyes elemei állnak elő. Ez o málisan a kö e kező de- iníció al ad am meg. 1. De iníció. Az mondjuk, hogy a τw◦aw◦kö szó ája, ha = 1· · · n∈w◦pon osan akko , ha lé eznek τw◦−ben olyan 0, ..., ncsomópon ok, hogy 7 • 0aτw◦ a gyöke e, nle élelem, és •minden i= 1, ..., nese én lé ezik a i−1csomópon ból icsomópon ba eze ő él, melynek címkéje i. Fákkal aló áb ázolás segí ségé el a Fibonacci sza akból képze kö sza ak ese én ismé lődő min á igyel em meg, mely a kö e kező ézis alapjául szolgál . 4. Tézis (Fibonacci kö sza akhoz a ozó ák hie a chiája [1,4]). Bá mely 2<i<jese én, τ( i)◦gyöké ből kiinduló ész ája a τ( j)◦ ának.  Azaz a ö idebb Fibonacci kö sza ak ái gyöké ből kiinduló ész akén sze epelnek a hosszabb Fibonacci kö sza ak áiban. Példakén a 2. áb á emelem ki. Ennek kö e kezményekén a ég elen Fibonacci szó ól a kö e kező állapí o am meg. 5. Tézis (A ég elen Fibonacci szó bizonyos ak o ai ól [1,4]). A ég elen Fibonacci szónak alamennyi ( i)◦−beli szó ak o a bá mely i∈N0ese én.  Ez alá ámasz ja, hogy a modell izsgála a a hagyományos modellek szempon jából sem elhanyagolha ó. A en emlí e on osabb e edmények melle a bizonyí á- sukhoz szükséges segéd é eleke és azok bizonyí ásai is a al- mazza a dolgoza . 8 nak ne ezzük. Ellenkező ese ben Ako lá lanul o duló au- oma a. Ahogy az alábbi ézis mu a ja, belá am, hogy lé ezik olyan egulá is nyel , melye éges sok számláló al nem ogad el egye len de e minisz ikus alós-idejű egyállapo ú 50→30 Wa son–C ick számlálóau oma a sem. 6. Tézis (De e minisz ikus számlálóau oma ák ko lá ai [2]). Az Lab ={(ab)n|n∈N}nyel e egye len de e minisz ikus alós-idejű egyállapo ú k− o duló m−számlálós au oma a sem ogadja el (k, m ≥1).  Megad am olyan négy számláló al endelkező au oma a de- iníciójá , amely el ogad egy nem kö nyeze ügge len, nem sze- milineá is nyel e . 7. Tézis (Egy szemilineá is, nem kö nyeze üggő nyel e el o- gadó au oma a [2]).Lé ezik olyan de e minisz ikus nem alós- idejű egyállapo ú 50→30Wa son–C ick számlálóau oma a, amely az L={an2|n≥0}nyel e ogadja el.  Melynek kö e kezménye, hogy a de e minisz ikus nem alós- idejű egyállapo ú 50→30Wa son–C ick számlálóau oma ák ál al el ogado nyel ek osz álya a almaz nem szemilineá is, így nem kö nyeze ügge len nyel e . 15 8. Tézis (Nemde e minisz ikus au oma ák ki ejezőe eje [7]). Lé ezik olyan nyel , melye el ogad egy nemde e minisz ikus alós-idejű egyállapo ú 1− o duló 1−számlálós au oma a, de egye len k, m ∈Nese én sem ogadja el egy de e minisz ikus alós-idejű egyállapo ú k− o duló m−számlálós au oma a.  Azaz az egyállapo ú 50→30Wa son–C ick számlálóau o- ma ák nemde e minisz ikus ál oza ainak ki ejezőe eje azonos pa amé e ek melle nagyobb, min a de e minisz ikus ál o- za oké. E edményeime a 3. áb án lá ha ó a almazási hie a chi- á al lehe áb ázolni. É elmezéséhez az alábbi jelölések be e- ze ése szükséges. Legyenek k, m ∈Nés k < 2m−1 m, ugyanis az au oma a implici e oldja meg a számlálók o dulásainak ko lá- ozásá . Jelölje WKk mak− o duló m−számlálós (nemde e mi- nisz ikus) nem alós-idejű au oma ák osz ályá , DWKk mpedig az azonos pa amé e ekkel endelkező de e minisz ikus au oma- ákból álló osz ály . Hasonlóan, end e WKVk més DWKVk mje- löli a alós-idejű, alamin a de e minisz ikus alós-idejű ész- halmazoka . To ábbá be eze jük a WK∞ mjelölés , amely a ko lá ozás nélkül o duló m-számlálós au oma áka jelöli és le- 16 gyen WK∞ ∗=[ m∈N WK∞ m. Ha Kegy au oma aosz ály, akko L(K)− al jelöljük az osz ályba a ozó au oma ák ál al el ogado nyel eke , azaz L(K) = {L(A)| A ∈ K}. 17 L(DWKV1 m) L(DWKVk m) L(WKk m) Reg L(WKV1 1) L(WKVk m) L(WK∞ ∗)(= RE) 3. áb a. Az áb án Reg jelöli a egulá is, RE pedig a eku zí elso olha ó nyel ek osz ályá . A nyilak alódi a almazás jelen enek, az á húzo onalak pedig az jelzik, hogy a ké nyel osz ály halmazelméle i a almazás ekin e nem össze- hasonlí ha ó, azaz mindké osz ályban annak olyan nyel ek, amelyek a másikban nem sze epelnek. Ha ké osz ály közö az áb án nincs jelöl e semmilyen eláció, akko annak eljes elde í ése még megolda lan elada . To ábbá a a almazási eláció anzi i i ása mia a edundáns nyilaka elhagy am. 18 Theses o he PhD disse a ion UNCONVENTIONAL MODELS IN THE THEORY OF FORMAL LANGUAGES AND AUTOMATA László Hegedüs Supe iso : D . Benedek Nagy UNIVERSITY OF DEBRECEN Doc o al School o In o ma ics 2016, Deb ecen 1 In oduc ion Du ing he las decades we can obse e a g owing in e es in uncon en ional models o compu a ion. The ield is as , since i consis s o all models ha a e di e en in one way o ano he om he ones desc ibed in classical echnical li e a u e [Hopc o e al., 2006]. Biology p o ed o be a majo sou ce o ideas. The cen al elemen o he ield is bioinspi ed compu ing which deals wi h he p ac ical and heo e ical applica ions o biological and chemical p ocesses obse ed inside li ing hings. My esea ch is based on wo models. In na u e we can ind ings o med om DNA s ands (e.g., mi ochond ial DNA) ha can be conside ed as a mo i a ion o analyzing he p ope ies o ci cula wo ds. Ne e heless, my app oach o ci cula wo ds is pu ely ma hema ical and in- dependen o he biological mo i a ion. The no ion o ci cula wo d is no new, o he esea che s in es iga ed ce ain p ope - ies o hem [Cu ie and Fi zpa ick, 2002, Dieke e al., 2006, Shu , 2010], bu I in oduced a new no ion o pe iodici y which lead o he disco e y o b and new esul s. The o he opic o my esea ch is he s a eless mul icoun e 50→30Wa son–C ick au oma on which is a special a ia ion o he well known Wa son–C ick au oma on o DNA compu ing. 1 The model is new and i has se e al pa ame e s ha a ec he exp essing powe signi ican ly. The e o e my esea ch a ge ed he hie a chy o accep ed languages based on hese pa ame e s. 2 P ima y goals and esul s 2.1 P ima y goals ega ding pe iodic p ope ies o ci cula wo ds The analysis o pe iodic p ope ies o wo ds goes back o he beginning o he 1900s when Axel Thue published his a icles abou squa e- ee wo ds [Thue, 1906, 1912]. The i s compila- ion o esul s in his a ea was w i en by a g oup o people un- de he pen name M. Lo hai e [Lo hai e, 1997]. Mos o hem we e s uden s o Ma cel P. Schü zenbe ge who is well known o his con ibu ions o his ield. All o he wo k men ioned abo e deals wi h o dina y (linea ) wo ds and a ely men ion ci cula wo ds, e en hough he ield has g ea po en ial and many in e es ing open ques ions. To in oduce my goals and esul s ega ding he opic o ci cula wo ds a couple o no- ions ha e o be de ined. I assume ha he eade is amilia wi h he basic no ions and no a ion o he heo y o o mal lan- guages and au oma a [Hopc o e al., 2006]. An in oduc o y 2 cou se should su ice. Two wo ds uand o e an alphabe Σ a e conjuga es i and only i he e exis x,y∈Σ∗such ha u=xy and =yx. Le w∈Σ∗. Then he ci cula wo d ob ained om wis he se o wo ds w◦={ ∈Σ∗| ∼w}. w3 w2 w1 wn wn−1. . . Figu e 1. Ci cula wo d In connec ion o ci cula wo ds he e exis s he ope a o σ(.)o cyclic shi . I w=w1w2· · · wn, hen σ(w) = w2· · · wnw1. Fu he mo e, σ0(w) = wand, i k∈N, hen σk(w) = σ(σk−1(w)). Le 0=b, 1=aand o all n≥2 n= n−1 n−2. The wo d i(i∈N0)is called he i h Fibonacci wo d [Smy h, 3 2003], and he ci cula wo d ob ained om i is he i h ci cu- la Fibonacci wo d. The leng h o hese wo ds ollow exac ly he se ies o Fibonacci numbe s. The limi o he se ies { i}∞ i=0 is usually e e ed o as he in ini e Fibonacci wo d. Rega ding he model o ci cula wo ds he goals o my wo k was o in es iga e and gi e answe s o he ollowing ques ions. 1. We say ha an in ege p > 0is a pe iod o he wo d wi and only i wi=wi+p o all i= 1, . .., |w|−p. How can he no ion o pe iod be gene alized o ci cula wo ds? 2. Is i possible o gi e a necessa y and su icien condi ion on he exis ence o a gi en gene alized pe iod? 3. The Pe iodici y Lemma o Na han J. Fine and He be S. Wil is one o he mos impo an esul s in combi- na o ics on wo ds [Lo hai e, 1997]. I desc ibes he ela- ion o wo a bi a y pe iods o a gi en wo d and s a es ha , i bo h pand qa e pe iods o he wo d wand p+q−lnko(p, q)≤ |w|, hen lnko(p, q)is also a pe iod o w. Is i possible o gene alize his esul o pe iods o ci cula wo ds? 4. Su ixes o o dina y wo ds a e o en ep esen ed by su ix ies [C ochemo e and Ry e , 2002]. How can we make use o simila hie a chical da a s uc u es in he ep e- 4 sen a ion o ci cula wo ds? 2.2 Resul s ega ding pe iodic p ope ies o ci cula wo ds He e I p esen he esul s o my wo k ega ding he p ob- lems and ques ions men ioned abo e. Using he no ion o pe- iod o o dina y wo ds I de ined he weak pe iod which is a pe iod o a leas one elemen o a gi en ci cula wo d. Tha is, he in ege p > 0is a weak pe iod o he ci cula wo d w◦ i and only i pis a pe iod o a leas one ∈w◦[6]. I ound and p o ed a necessa y and su icien condi ion o a gi en in ege p o be a weak pe iod o a gi en ci cula wo d w◦[1]. This esul is gi en by he ollowing Thesis. Thesis 1 (A necessa y and su icien condi ion o he exis- ence o a ce ain weak pe iod [1]).Le w∈Σ∗be an a bi a y wo d. I pis a weak pe iod o w◦, hen he e exis s a wo d x∈Σ∗o leng h |w| − pand an in ege `∈N0, such ha σ`(x)xis a ac o o ww. Con e sely, he ollowing a e ue: I. I ww has a ac o xx (x∈Σ+), such ha |x|<|w|, hen p=|w|−|x|is a weak pe iod o w◦. II. I he e exis s an in ege p > 0, such ha he ollowing 5 m)∈δ(a, b, s), ha is, i is no possible o dec ease a coun e whose alue is ze o. I de ined he con igu a ions and a ela ion o e con igu a- ions ha desc ibe he compu a ion o an au oma on in a way ha p ohibi s he eading heads o c oss each-o he . The pai C= (w, s)∈ {¢, λ}Σ∗{$, λ} × Nm 0is a con igu a- ion o he au oma on A. The con igu a ion C2= (w0, s0)=(w0, s0 1, . . . , s0 m) is di ec ly accessible om con igu a ion C1= (w, s) = (w, s1, . . . , sm) (deno ed by: C1`AC2), i and only i one o he ollowings is sa is ied: •w=aw0b,|w| ≥ 2and (1,1, 1, .. ., m)∈δ(a, b, sign(s)), •w=aw0=ub o some u∈Σ∗,|w| ≥ 1and (1,0, 1, .. ., m)∈δ(a, b, sign(s)), •w=w0b=au o some u∈Σ∗,|w| ≥ 1and (0,1, 1, .. ., m)∈δ(a, b, sign(s)), •w=au= b=w0 o some u, ∈Σ∗,|w| ≥ 1and (0,0, 1, .. ., m)∈δ(a, b, sign(s)), •w=λ=w0and (0,0, 1, .. ., m)∈δ(λ, λ, sign(s)), 12 u he mo e, s0 i=        si+ 1 ,i i= +, si−1,i si>0and i=−, si,o he wise ( ha is, i i= 0), o all i= 1, .. ., m. The language accep ed by Ais de ined as L(A) = {w∈Σ∗|(¢w$,0m)`∗(λ, 0m)}. De ini ion 3. A s a eless mul icoun e 50→30Wa son–C ick au- oma on is eal ime i and only i o all a,b∈(Σ ∪ {¢,$}), s∈ {0,1}m he ollowing is ue δ(a, b, sign(s)) ⊆(d1, d2, )∈ {0,1}2× {0,+,−}m|d1+d2≥1. Tha is, a leas one o he eading heads mo e in each an- si ion. I his condi ion is no equi ed o be sa is ied, hen we call he au oma on non- eal ime. A s a eless mul icoun e 50→30Wa son–C ick au oma on is de e minis ic i and only i o all a,b∈(Σ ∪ {¢,$})and s∈ {0,1}m,|δ(a, b, sign(s))| ≤ 1. Le be a coun e and C1`. .. `C`a se ies o con igu- a ions which is also called a compu a ion. The beha io o can be obse ed du ing any compu a ion ega ding he changes 13 be ween non-dec easing and dec easing phases, i.e., when he alue o he coun e is dec eased a e se e al s eps o inc ease and unchange ope a ions. I his happens o a mos k imes in any compu a ion, hen we say ha is a k− e e sal coun e . I no such kexis s, hen is a e e sal unbounded coun e . I he e exis s an in ege k, such ha all coun e s o A a e (a mos ) k− e e sal, hen Ais a k− e e sal au oma on. O he wise, Ais a e e sal unbounded au oma on. As he ollowing hesis shows, I p o ed ha he e exis s a egula language ha canno be accep ed by any ini e numbe o coun e s by a de e minis ic s a eless mul icoun e 50→30 Wa son–C ick au oma on. Thesis 6 (Limi s o de e minis ic s a eless mul icoun e 50→30 Wa son–C ick au oma a [2]).The language Lab ={(ab)n|n∈ N}canno be accep ed by any de e minis ic eal ime k− e e sal m−coun e 50→30Wa son–C ick au oma on o any k, m ≥1. I also de ined a de e minis ic s a eless mul icoun e 50→30 Wa son–C ick au oma a wi h ou coun e s ha accep s a non- con ex - ee semilinea language. Thesis 7 (Accep ing a non-con ex - ee semilinea language [2]).The e exis s a de e minis ic non- eal ime s a eless mul- 14 icoun e 50→30Wa son–C ick au oma on ha accep s he language L={an2|n≥0}. Thus he class o languages accep ed by de e minis ic non- eal ime s a eless mul icoun e 50→30Wa son–C ick au oma a con ains a semilinea non-con ex - ee language. Thesis 8 (The exp essi e powe o nonde e minis ic au oma a [7]).The e exis s a language ha can be accep ed by a nonde e - minis ic eal ime 1− e e sal 1−coun e au oma a, bu canno be accep ed by any de e minis ic eal ime k− e e sal m−coun e au oma on o any k, m ∈N. Tha is, he exp essi e powe o nonde e minis ic s a eless mul icoun e 50→30Wa son–C ick au oma a is g ea e han ha o hei de e minis ic coun e pa s. My esul s a e summa ized on Figu e 3. Le k, m ∈N and k < 2m−1 m, since he au oma a implici ly sol es e e sal boundedness. Le WKk mdeno e he class o non- eal ime (non- de e minis ic) k− e e sal m−coun e au oma a, while DWKk m is he class o de e minis ic au oma a wi h he same pa am- e e s. Simila ly, WKVk mand DWKVk mdeno es espec i ely he eal ime and de e minis ic eal ime classes. Fu he mo e, we in oduce he no a ion WK∞ m ha is he class o e e sal 15 unbounded m−coun e au oma a and le WK∞ ∗=[ m∈N WK∞ m. I Kis a class o au oma a, hen L(K)deno es he se o languages accep ed by au oma a ha belong o K, ha is, L(K) = {L(A)| A ∈ K}. 16 L(DWKV1 m) L(DWKVk m) L(WKk m) Reg L(WKV1 1) L(WKVk m) L(WK∞ ∗)(= RE) Figu e 3. Reg and RE deno es he class o egula and ecu - si e enume able languages, espec i ely. A ows deno e s ic inclusion, while s ike- h ough lines deno e ha he wo classes a e incompa able ( om a se heo e ic poin o iew), ha is, bo h classes con ain a leas one language ha he o he does no . I no ela ion is p esen ed be ween wo classes, hen i is an open p oblem o desc ibe hei ela ion. The a ows (like he ela ions hey deno e) a e ansi i e, hus he edundan ones a e no d awn. 17 I odalomjegyzék / Re e ences Maxime C ochemo e and Wojciech Ry e . Jewels o S ingology: Tex Algo i hms. Wo ld Scien i ic, Hack- ensack, NJ, USA, 2002. James D. Cu ie and Daniel S. Fi zpa ick. Ci cula wo ds a oiding pa e ns. P oceedings o he 6 h In e na ional Con e ence on De elopmen s in Language Theo y. LNCS, 2450:319–325, 2002. Volke Dieke , Te o Ha ju, and Di k Nowo ka. Fac o iza ions o cyclic wo ds. Wo kshop on Wo ds and Au oma a a CSR, 7, 2006. Pál Dömösi, János Falucskai, Géza Ho á h, Zol án Mecsei, and Benedek Nagy. Fo mális nyel ek és au oma ák. Deb eceni Egye em, jegyze , 2011. Öme Eğecioğlu and Osca H. Iba a. On s a eless mul i- coun e machines. In P oceedings o 5 h Con e ence on Compu abili y in Eu ope 2009, numbe 5635 in Lec u e No es in Compu e Science, pages 178–187. Sp inge Be lin Heidelbe g, 2009a. Öme Eğecioğlu and Osca H. Iba a. On s a eless mul i- coun e machines. In P oceedings o 15 h In e na ional 18 Compu ing and Combina o ics Con e ence, numbe 5609 in In e na ional Compu ing and Combina o ics Con- e ence, Lec u e No es in Compu e Science, pages 408–417. Sp inge Be lin Heidelbe g, 2009b. John E. Hopc o , Rajee Mo wani, and Je ey D. Ullman. In oduc ion o Au oma a Theo y, Languages, and Compu a ion, 3 d ed. Addison-Wesley, 2006. János Kiss. Biológiai kislexikon. Typo ex Elek onikus Ki- adó K , 2007. M. Lo hai e. Combina o ics on Wo ds. Camb idge Ma hema ical Lib a y. Camb idge Uni e si y P ess (1983, Addison-Wesley), 1997. Ma in L. Minsky. Compu a ion: Fini e and In ini e Ma- chines. P en ice-Hall, Inc., Uppe Saddle Ri e , NJ, USA, 1967. Benedek Nagy. On 50→30sensing Wa son-C ick ini e au- oma a. In 13 h In e na ional Mee ing on DNA Com- pu ing, olume Lec u e No es in Compu e Science, 4848 o In e na ional Mee ing on DNA Compu ing, pages 256–262. Sp inge Be lin Heidelbe g, 2008. 19 A seny M. Shu . On e na y squa e- ee ci cula wo ds. The Elec onic Jou nal o Combina o ics, 17, 2010. William F. Smy h. Compu ing Pa e ns in S ings. ACM P ess. Pea son Addison-Wesley (UK), 2003. Axel Thue. Übe unendliche Zeichen eihen. No ske Vid. Sk i e I Ma .-Na . Kl., Ch is iania, 1:1–22, 1906. Axel Thue. Übe die gegensei ige Lage gleiche Teile gewisse Zeichen eihen. No ske Vid. Sk i e I Ma .-Na . Kl., Ch is iania, 1:1–67, 1912. 20 DEBRECENI EGYETEM E GYETEMI ÉS N EMZETI K ÖNYVTÁR Cím: 4032 Deb ecen, Egye em é 1. ¤ Pos acím: 4010 Deb ecen, P . 39. ¤ Tel.: (52) 410-443 E-mail: [email protected] ¤ Honlap: www.lib.unideb.hu Jelöl : Hegedüs László Nep un kód: YU4N37 Dok o i Iskola: In o ma ikai Tudományok Dok o i Iskola MTMT azonosí ó: 10037392 A PhD é ekezés alapjául szolgáló közlemények Idegen nyel ű udományos közlemény(ek) kül öldi olyói a ban (3) 1. Hegedüs, L., Nagy, B.: On pe iodic p ope ies o ci cula wo ds. Disc e . Ma h. 339 (3), 1189-1197, 2016. ISSN: 0012-365X. DOI: h p://dx.doi.o g/10.1016/j.disc.2015.10.043 IF:0.557 (2014) 2. Hegedüs, L., Nagy, B., Eǧecioǧlu, Ö.: S a eless Mul icoun e 5'->3' Wa son-C ick au oma a: The de e minis ic case. Na Compu . 11 (3), 361-368, 2012. ISSN: 1567-7818. DOI: h p://dx.doi.o g/10.1007/s11047-011-9290-9 IF:0.683 3. Nagy, B., Hegedüs, L., Eğecioğlu, Ö.: Hie a chies o S a eless Mul icoun e 5’ -> 3’ Wa son-C ick Au oma a Languages. Fundam. In o m. 110, 1-13, 2011. ISSN: 0169-2968. DOI: h p://dx.doi.o g/10.3233/FI-2011-553 IF:0.365 Idegen nyel ű kon e encia közlemény(ek) (5) 4. Hegedüs, L., Nagy, B.: Rep esen a ions o Ci cula Wo ds. Elec on. P oc. Theo . Compu . Sci. 151, 261-270, 2014. EISSN: 2075-2180. DOI: h p://dx.doi.o g/10.4204/EPTCS.151.18 Nyil án a ási szám: DEENK/87/2016.PL Tá gy: PhD Publikációs Lis a