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