Soliton automata: a computational model on the principle of graph matchings

Soliton automata: a computational model on the principle of graph matchings Doktori ´ertekez´es t´ezisei

Kr´esz Mikl´os

T´emavezet˝o:

Dr. Bartha Mikl´os Egyetemi Docens

Szegedi Tudom´anyegyetem 2004

2

1

Bevezet´ es A molekul´aris sz´am´ıt´ asok elm´elete napjainkban egy gyorsan fejl˝ od˝ o ir´anyzat mind az elm´eleti mind az alkalmaz´as-orient´alt kutat´ asok ter´en ([1],[27], [30]). Az egyik leg´ıg´eretesebbnek t˝ un˝ o alternat´ıva a hagyom´ anyos komputertechnol´ ogi´ aval szemben az u ´ gynevezett bioelektronika vagy molekul´ aris elektronika ([28]). A bioelektronikus eszk¨oz¨ok tervez´ese kapcs´an az egyik leg´erdekesebb javaslattal F. L. Carter a´llt el˝o ([9]) az 1980-as ´evekben. A Carter koncepci´oj´ an alapul´ o u ´gynevezett szoliton ´ aramk¨ or¨okben a k´emiai komponenseket mint molekul´aris szint˝ u kapcsol´oelemeket sz´enhidrog´enmolekulal´ancokkal k¨otn´ek ¨ossze, ´es az ezen l´ancokon v´egigvonul´ o u ´gynevezett ”szoliton hull´ amz´as” realiz´aln´ a az elektronikus kapcsol´asokat. A szoliton ´aramk¨ or¨ ok fejleszt´ese ter¨ ulet´en az 1990-es ´evekben jelent˝ os k´ıs´erletek folytak ( [19], [20], [21], ´es [22]), melynek sor´an felmer¨ ult az ig´eny, hogy egy alkalmas matematikai elm´elettel t´amogass´ak ezen kapcsol´oh´ al´ ozatok fejleszt´es´et ´es majdani verifik´ aci´oj´ at. Azonban M. P. Groves egy korai munk´ aj´ at lesz´am´ıtva ([18]) nem t¨ort´ent el˝orehalad´ as a fenti t´emak¨orben. Ezen disszert´aci´o a szoliton ´aramk¨ or¨ ok matematikai modellj´enek, a szoliton automat´anak a vizsg´alat´ aval foglalkozik. A szoliton automata defin´ıci´ oja J¨ urgen Dassow ´es Helmut J¨ urgensen ([10]) nev´ehez f˝ uz˝ odik, akik a fenti modellt annak ´erdek´eben alkott´ ak meg, hogy a ”szoliton hull´ amok” kapcsol´oelemk´ent val´ o felhaszn´alhat´ os´ag´ at form´alis matematikai keretek k¨oz¨ott lehessen vizsg´alni. Dassow ´es J¨ urgensen u ´tt¨ or˝ o munk´ aj´ at sz´amos tov´abbi publik´ aci´o k¨ovette a t´em´aban. A [11], [12] ´es [13] dolgozatokban a determinisztikus szoliton automat´ak n´eh´ any fontos speci´alis esete ker¨ ult le´ır´ asra a transzform´aci´os monoid seg´ıts´eg´evel. Egy m´asik megk¨ozel´ıt´es alapj´an az er˝osen determinisztikus szoliton automat´ak homomorfan teljes oszt´alyait jellemezte G´ecseg ´es J¨ urgensen ([17]). Azonban egy olyan elm´elet kifejleszt´ese tov´abbra o szoliton gr´afok is v´aratott mag´ara, amely az alapobjektumk´ent szolg´al´ strukt´ ur´ alis le´ır´ asa seg´ıts´eg´evel alapot szolg´altatott volna a szoliton automat´ak tov´ abbi anal´ızis´ehez. A fentiek mutatj´ ak, hogy mind az automatelm´elet, mind az ´aramk¨ or¨ ok tervez´ese szempontj´ab´ ol k¨ozponti k´erd´es egy strukt´ ur´ alis elm´elet kidolgoz´asa. Ezen dolgozat motiv´aci´oj´ at a fenti felismer´es adta ´es c´elk´ent fogalmaz´odott meg, hogy a szoliton gr´ afok ´es ennek alapj´an a szoliton automat´ak egy r´eszletes strukt´ ur´ alis le´ır´ as´at adjuk meg. A disszert´aci´oban szerepl˝o elm´eleti eredm´enyek algoritmikus k¨ ovetkezm´enyeit is felv´azoljuk, ami

2 a szoliton ´aramk¨ or¨ ok tervez´es´eben ´es verifik´ aci´oj´ aban nyithat u ´j t´avlatokat. A t´ezisek er˝osen t´amaszkodnak az [4], [5], [6], [7], [8] ´es [25] munk´ ainkra. A [4]-ban k¨ oz¨olt eredm´enyek k¨oz¨ ul n´eh´anyat a disszert´aci´oban ´altal´ anosabb form´aban mondunk ki ´es az algoritmikus k¨ovetkezm´enyeit is t´argyaljuk.

Szoliton automat´ ak ´ es a p´ aros´ıt´ asok elm´ elete A szoliton automat´ak anal´ızis´et a gr´afokban ´ertelmezett p´aros´ıt´ asok elm´elet´ere t´amaszkodva v´egezz¨ uk el. Egy p´ aros´ıt´ as alatt a gr´af ´eleinek egy olyan M r´eszhalmaz´at ´ertj¨ uk, melyre igaz, hogy M k¨ ul¨ onb¨ oz˝o elemeinek nincs k¨oz¨os v´egpontja. A szoliton automat´ ak ´es a p´aros´ıt´ asok kapcsolat´ara M. Bartha ´es E. Gomb´ as mutatott r´a a [3] dolgozatban. A szoliton automata alapobjektuma az u ´gynevezett szoliton gr´af, amely a megfelel˝o molekulal´anc topol´ogiai le´ır´ as´ara szolg´al. Ebben a modellben a gr´af cs´ ucspontjai az atomoknak (vagy az atomok egy csoportj´ anak) felelnek meg, m´ıg a k´emiai k¨ot´eseket a gr´af ´elei reprezent´alj´ ak. Azon cs´ ucspontokat melyek foksz´ama 1 u ´gynevezett k¨ uls˝ o cs´ ucsokk´ent k¨ ul¨ onb¨ oztetj¨ uk meg, m´ıg azon cs´ ucsok, melyek foksz´ama legal´abb 2, bels˝ o cs´ ucsoknak nevezz¨ uk. A ul az k¨ uls˝ o cs´ ucsok a rendszer interf´eszek´ent szolg´alnak, amelyen kereszt¨ elektronok el´erhetik a molekulah´ al´ ozat bels˝o strukt´ ur´ aj´ at. A bels˝o cs´ ucsok olyan atomoknak (vagy atomok egy csoportj´ anak) felelnek meg, melyek pontosan egy szomsz´edjukhoz kapcsol´ odnak kett˝ os k¨ot´essel. Ezt a tulajdons´agot a gr´afmodellben a teljes bels˝ o p´ aros´ıt´ asokkal ´ırhatjuk le, azaz olyan p´ aros´ıt´ asokkal, melyek minden bels˝o cs´ ucsot lefednek. A fentiekb˝ ol ad´od´ oan egy szoliton gr´ afot egy olyan gr´afk´ent defini´ alhatunk, amely tartalmaz egy k¨ uls˝ o cs´ ucsot, valamint rendelkezik egy teljes bels˝o p´aros´ıt´ assal. Egy szoliton gr´af teljes bels˝o p´aros´ıt´ asaira ´ allapotokk´ent is hivatkozunk, utalva a megfelel˝o molekulal´anc modellezett ´allapotaira. A G szoliton gr´af ´allapotainak (teljes bels˝ o p´aros´ıt´ asainak) halmaz´at S(G) jel¨oli. A szoliton ´atmenetek le´ır´ asa ´erdek´eben a gr´afmodellen defini´ alunk egy speci´alis altern´al´ o s´et´at, az u ´gynevezett szoliton s´et´at, amely azt a hat´ast reprezent´alja, amint egy szoliton hull´ am az u ´ tja sor´an felcser´eli a kett˝os ´es egyes k¨ot´eseket a sz´enhidrog´en-molekulal´ ancban. A megfelel˝o gr´afelm´eleti formalizmus ´erdek´eben vezess¨ uk be a k¨ovetkez˝o jel¨ol´est: egy tetsz˝oleges α = asainak v0 , e1 , . . . , en , vn s´eta eset´en jel¨olje nα (j) (j ∈ [n]) az ej ´el el˝ofordul´ a sz´am´at az α[v0 , vj ] = v0 , e1 , . . . , ej , vj prefixben. Defin´ıci´ o. A G szoliton gr´af egy M ´allapot´ara vonatkoz´ o parci´ alis szoliton s´eta alatt egy olyan visszal´ep´es-mentes α = v0 , e1 , . . . , en , vn (n ≥ 1) s´et´at ´ert¨ unk, melyre ´erv´enyesek az al´abbiak:

3 uls˝ o cs´ ucs; (a) v0 egy k¨ (b) b´ armely j ∈ [n − 1] eset´en, nα (j) ´es nα (j + 1) parit´ asa akkor ´es csakis al´ o; azaz ej ∈ M ´es ej+1 ∈ M akkor egyezik meg, ha ej ´es ej+1 M -altern´ csak egyszerre ´allhat fenn. Tov´ abb´ a, egy parci´alis szoliton s´et´at szoliton s´et´ anak nevez¨ unk, ha a fenti defin´ıci´ oban vn szint´en k¨ uls˝ o cs´ ucs. Az α s´eta M ´allapotban t¨ ort´en˝ o realiz´ al´ asa alatt azt ´ertj¨ uk, hogy l´etrehozzuk az S(M, α) ´elhalmazt a k¨ovetkez˝ok´eppen: B´armely e ∈ V (G) eset´en, e ∈ S(M, α) akkor ´es csakis akkor, ha vagy e ∈ M ´es e p´ aros sokszor szerepel az α s´et´aban, vagy e ∈ M ´es e p´aratlan sokszor szerepel az α-ban. Igazolhat´ o, hogy amennyiben α egy szoliton s´eta, akkor S(M, α) szint´en egy teljes bels˝o p´aros´ıt´ as lesz. Tov´abb´ a az is vil´agos, hogy a j´ arhatatlan ´elek – olyan ´elek melyek nem szerepelnek egy parci´alis szoliton s´et´aban sem – nem befoly´asolj´ ak a rendszer m˝ uk¨ od´es´et. Ez´ert b´armely G szoliton gr´af eset´en, csak a j´ arhat´ o ´elek (olyan ´elek, melyek nem j´arhatatlanok) j´atszanak szerepet a szoliton automat´ak le´ır´ as´aban. A fenti ´eszrev´etelek adj´ak a motiv´aci´ot, hogy defini´ aljuk egy tetsz˝oleges G szoliton gr´af G+ j´ arhat´ o r´eszgr´ afj´ at, amely alatt a j´arhat´ o ´elek ´altal meghat´arozott gr´afot ´ertj¨ uk. K¨ onnyen bel´ athat´ o, hogy G+ szint´en szoliton gr´af. A szoliton automata form´alis defin´ıci´ oj´ ahoz sz¨ uks´eg¨ unk lesz egy tov´ abbi jel¨ol´esre: uls˝ o Egy G szoliton gr´af b´armely M ´ allapota ´es tetsz˝oleges v1 , v2 ∈ V (G) k¨ cs´ ucsok eset´en jel¨olje o szoliton s´eta, amely SG (M, v1 , v2 ) = {S(M, α) | α egy M -re vonatkoz´ v1 -b˝ol indul ´es v2 -ben fejez˝odik be} Defin´ıci´ o. A G gr´ afhoz tartoz´o A(G) = ((S(G+ ), (X × X), δ) szoliton automata alatt azt a nemdeterminisztikus v´eges automat´at ´ertj¨ uk, melyre a k¨ovetkez˝ok ´allnak fenn. (a) G egy szoliton gr´af, allapothalmaz´aval egyezik (b) A(G) ´allapotainak S(G+ ) halmaza a G+ ´ meg, (c) (X × X) az input a´b´ec´e, ahol X jel¨ oli G k¨ uls˝ o cs´ ucsainak a halmaz´at, (d) a δ : S(G+ ) × (X × X) → 2S(G defini´ alt:

+)

´atmenetf¨ uggv´eny a k¨ovetkez˝ok´epp

4


δ(M, (v1 , v2 )) =

SG+ (M, v1 , v2 ), ha SG+ (M, v1 , v2 ) = ∅ {M }, egy´ebk´ent

b´ armely M ∈ S(G+ ) ´es v1 , v2 ∈ X eset´en.

Szoliton gr´ afok Tutte t´ıpus´ u jellemz´ ese Ebben a r´eszben a [2] cikk eredm´enyeit er˝os´ıtj¨ uk. A fenti munka Tutte t´etel´enek ([29]) teljes bels˝o p´aros´ıt´ asokra vonatkoz´ o megfelel˝oj´et t´argyalja. A klasszikus gr´afelm´eletben korl´ athalmaznak (barrier) nevezz¨ uk azokat a cs´ ucshalmazokat, melyekre a Tutte-Berge formul´aban egyenl˝ os´eg ´all fenn ([26]). Ezen fogalom nem terjeszthet˝o ki anal´ og m´odon bels˝o p´aros´ıt´ asokra, de az u ´ gynevezett sz´etv´alaszt´o halmazok hasonl´o tulajdons´ agokat mutat´ nak, amennyiben maxim´ alisak. Eszrev´ eteleinket k´et Tutte t´ıpus´ u t´etelben foglaljuk o¨ssze. Eredm´enyeink megfogalmaz´as´ahoz sz¨ uks´eg¨ unk van n´eh´any u ´jabb defin´ıci´ora . Adott G szoliton gr´af eset´en azt mondjuk, hogy egy e ´el megengedett (k¨ otelez˝ o), ha e szerepel G valamely (¨osszes) teljes bels˝o p´aros´ıt´ as´aban. A nem megengedett ´eleket tiltott ´eleknek nevezz¨ uk. A G gr´ af bels˝o cs´ ucsainak egy nem¨ ures X halmaz´at sz´etv´ alaszt´ o halmaznak nevezz¨ uk, ha X b´armely k´et cs´ ucs´at egy e ´ellel ¨osszek¨otve az e tiltott lesz a G + e gr´ afban. Legyen M a G gr´af egy teljes bels˝o p´aros´ıt´ asa. A G gr´af egy e ´el´et M pozit´ıvnak (M -negat´ıvnak) nevezz¨ uk, ha e ∈ M (illetve, ha e ∈ M ). Egy M -altern´ al´ o vonal a G gr´ afban egy olyan vonal, melyben M -pozit´ıv ´es M negat´ıv ´elek v´altakoznak. Azt mondjuk, hogy a v bels˝o cs´ ucs el´erhet˝ oaw ol v-be vezet˝o altern´al´ o k¨ uls˝ o cs´ ucsb´ ol az M ´allapotban, ha l´etezik egy w-b˝ u ´t, amely v-n´el pozit´ıv ´elben v´egz˝odik. El´erhet˝ o cs´ ucsok alatt azon cs´ ucsokat ´ertj¨ uk, amelyek el´erhet˝ oek egy k¨ uls˝ o cs´ ucsb´ol a G valamely ´allapot´aban. A faktor-kritikus gr´ afok ([26]) fogalma szint´en term´eszetes m´odon ´altal´ anos´ıthat´ o: Egy ¨osszef¨ ugg˝ o G gr´ afot faktor-kritikusnak nevez¨ unk, ha G minden v bels˝o cs´ ucs´ahoz l´etezik egy olyan p´aros´ıt´ as, amely a bels˝o cs´ ucsok k¨oz¨ ul csak v-t hagyja szabadon. V´eg¨ ul, a bels˝o cs´ ucsok b´armely X halmaza eset´en a G−X egy ¨osszef¨ ugg˝ o komponens´et akkor nevezz¨ uk degener´ altnak, ha mind¨ ossze egy k¨ uls˝ o cs´ ucsb´ ol ´all. 1. T´ etel.([8]) Legyen X a G szoliton gr´ af bels˝ o cs´ ucsainak egy nem¨ ures osszef¨ ugg˝ o komponenseinek a halmaza, ´es jel¨ olje cin (G, X) a G − X azon ¨ sz´ am´ at, melyek csak bels˝ o cs´ ucsokat tartalmaznak. Ekkor a k¨ ovetkez˝ o k´et ´ all´ıt´ as ekvivalens.

5 (i) X egy maxim´ alis sz´etv´ alaszt´ o halmaz. (ii) G − X minden nem degener´ alt ¨ osszef¨ ugg˝ o komponense egy faktorkritikus gr´ afot alkot, valamint (iia) |X| = cin (G, X) + 1, vagy (iib) |X| = cin (G, X) ´es G − X minden k¨ uls˝ o cs´ ucsot tartalmaz´ o komponense degener´ alt. Tov´ abb´ a, az (iib) felt´etel akkor ´es csak akkor ´ all fenn, ha X nem tartalmaz el´erhet˝ o cs´ ucsot. 2. T´ etel.([8]) Egy k¨ uls˝ o cs´ uccsal rendelkez˝ o G gr´ af akkor ´es csakis akkor szoliton gr´ af, ha a bels˝ o cs´ ucsainak b´ armely X r´eszhalmaza eset´en fenn´ all a otlens´eg, ahol coin (G, X) jel¨ oli G − X azon k¨ uls˝ o cs´ ucs coin (G, X) ≤ |X| egyenl˝ n´elk¨ uli ¨ osszef¨ ugg˝ o komponenseinek a sz´ am´ at, amelyek p´ aratlan sz´ am´ u bels˝ o cs´ ucsb´ ol ´ allnak. Egyenl˝ os´eg akkor ´es csakis akkor ´ allhat fenn egy nem¨ ures X-re, ha G nem minden ¨ osszef¨ ugg˝ o komponense k¨ uls˝ o cs´ ucsot tartalmaz´ o faktor-kritikus gr´ af. Ebben az esetben b´ armely olyan sz´etv´ alaszt´ o halmaz biztos´ıtja az egyenl˝ os´eget, amely maxim´ alis arra vonatkoz´ olag, hogy nem tartalmaz el´erhet˝ o cs´ ucsot. A fenti k´et eredm´eny kombin´ al´ as´aval a faktor-kritikus gr´ afok egy jellemz´es´et kapjuk. 3. T´ etel([8]) Egy k¨ uls˝ o cs´ ucsot tartalmaz´ o¨ osszef¨ ugg˝ o gr´ af akkor ´es csakis akkor faktor-kritikus, ha a bels˝ o cs´ ucsok b´ armely nem¨ ures X r´eszhalmaz´ ara otlens´eg. Ebben az esetben az fenn´ all a coin (G, X) ≤ |X| − 1 egyenl˝ egyenl˝ os´eget b´ armely maxim´ alis sz´etv´ alaszt´ o halmaz biztos´ıtja.

Szoliton gr´ afok strukt´ ur´ alis elm´ elete Automat´ak kompoz´ıci´ oja ´es dekompoz´ıci´ oja az 1960-as ´evekt˝ol intenz´ıven tanulm´ anyozott t´emak¨ore a sz´am´ıt´ astudom´ anynak. Ezen kutat´ asok f˝o c´elja, hogy a komplex rendszereket egyszer˝ ubb automat´ ak szorzatak´ent jellemezze. Annak ´erdek´eben, hogy ezt a feladatot szoliton automat´ ak eset´eben is megoldjuk, el˝osz¨or a szoliton gr´afok egy olyan dekompoz´ıci´ oj´ at kell v´egrehajtanunk, amelyben a komponens gr´ afokra ´ep¨ ul˝ o automat´ak r´eszben f¨ uggetlen¨ ul k´epesek m˝ uk¨ odni ´es megadhat´o a komponensek kapcsolat´anak egy form´alisan le´ır´ asa. A fenti c´elok ´erdek´eben egy strukt´ ur´ alis elm´eletet fejlesztett¨ unk ki, amely a szoliton gr´ afok elemi komponenseire ´ep¨ ul. A teljes bels˝o p´aros´ıt´ assal rendelkez˝o G gr´af elemi komponensei alatt a G olyan maxim´alis r´eszgr´afjait ´ertj¨ uk, amelyeket kiz´ar´ olag megengedett ´elek

6 fesz´ıtenek ki. Egy elemi komponenst k¨ uls˝ o vagy bels˝ o komponensnek h´ıvunk att´ol f¨ ugg˝ oen, hogy tartalmaz-e k¨ uls˝ o cs´ ucsot. Egy gr´af elemi, ha egyetlen elemi komponensb˝ol ´all. A teljes p´ aros´ıt´ asok (olyan p´ aros´ıt´ asok, melyek minden cs´ ucsot lefednek) elm´elet´eb˝ ol j´ol ismert ([26]), hogy az elemi gr´afok cs´ ucshalmaz´an defini´ alhat´ o egy kanonikus oszt´alyoz´ as. Ezt az eredm´enyt teljes bels˝o p´aros´ıt´ asokkal rendelkez˝o elemi gr´afokra a´ltal´ anos´ıtott´ ak a [3] dolgozat szerz˝oi. Ezen r´esz els˝o t´ezisek´ent a fenti oszt´alyoz´ ast kiterjesztj¨ uk minden olyan gr´af eset´ere, amely rendelkezik teljes bels˝o p´aros´ıt´ assal. Defin´ıci´ o. Legyen G egy teljes bels˝o p´aros´ıt´ assal rendelkez˝o gr´af. Ekkor tetsz˝oleges k´et u, v ∈ V (G) bels˝o cs´ ucs eset´en, u ∼ v amennyiben l´etezik egy sz´etv´alaszt´o halmaz, amely mindk´et cs´ ucsot tartalmazza ´es az u a v-vel azonos elemi komponensbe esik. 4.T´ etel([6]) A ∼ rel´ aci´ o egy ekvivalencia rel´ aci´ o a G bels˝ o cs´ ucsainak halmaz´ an. A ∼ rel´aci´ot kanonikus ekvivalenci´ anak nevezz¨ uk, m´ıg a ∼ ´altal meghat´arozott oszt´alyokra kanonikus oszt´ alyokk´ent hivatkozunk. A fenti oszt´alyoz´as alapj´an a j´arhat´ o ´eleket tartalmaz´o elemi komponensek (j´ arhat´ o elemi komponensek) egy olyan strukt´ ur´ aba rendezhet˝oek, amely strukt´ ura t¨ ukr¨ ozi a komponensek k¨ uls˝ o cs´ ucsb´ ol indul´ o altern´al´ o utak (k¨ uls˝ o altern´ al´ o utak) ´altal t¨ort´en˝ o el´erhet˝ os´eg´et. Ezen eredm´enyeinket az al´abbi t´etel ¨osszegzi. af j´ arhat´ o elemi komponensei diszjunkt 5. T´ etel.([6]) Egy G szoliton gr´ csal´ adokba rendezhet˝ oek a k¨ ovetkez˝ o m´ odon. (i) B´ armely csal´ ad legfeljebb egy k¨ uls˝ o elemi komponenst tartalmaz. (ii) Minden F csal´ ad amely csak bels˝ o komponensekb˝ ol ´ all pontosan egy olyan P kanonikus oszt´ alyt tartalmaz, amelyet b´ armely olyan k¨ uls˝ o altern´ al´ ou ´t ´erint, amely az F valamely tagj´ ahoz vezet. Tov´ abb´ a b´ armely k¨ uls˝ o altern´ al´ ou ´t ezen u ´gynevezett princip´ alis oszt´ alyt ´erinti el˝ osz¨ or a csal´ adon bel¨ ul. ∗

o ki a csal´ adok k¨ oz¨ ott, amelyben a (iii) Egy → r´eszbenrendez´es alak´ıthat´ rendez´esi rel´ aci´ ot az a sorrend defini´ alja, amint egy tetsz˝ oleges k¨ uls˝ o altern´ al´ ou ´t a csal´ adokat ´erinti. A r´eszbenrendez´es maxim´ alis elemei azon csal´ adok, amelyek tartalmaznak k¨ uls˝ o cs´ ucsot. (iv) Egy j´ arhat´ o elemi komponenshez tartoz´ o cs´ ucs akkor ´es csakis akkor nem el´erhet˝ o, ha egy princip´ alis kanonikus oszt´ alyban fekszik.

7 A fenti strukt´ ura kialak´ıt´ asa ut´an sz´etv´alaszt´o halmazok ´es faktorkritikus gr´ afok seg´ıts´eg´evel jellemezz¨ uk a csal´adokat, majd ezen eredm´enyek felhaszn´al´ as´aval megadunk egy algoritmust, amely az ´elek sz´am´aban line´ aris + arhat´ o r´eszgr´afj´ at, id˝oben meghat´arozza b´armely G szoliton gr´af G j´ tov´ abb´ a kialak´ıtja a csal´adokat ´es a csal´adok k¨oz¨otti r´eszbenrendez´est. Az elj´ar´ as az Edmonds algoritmusnak ([14]) egy m´ odos´ıtott v´altozata. arhat´ o r´eszgr´ af ´es 6. T´ etel([5]) B´ armely G szoliton gr´ af eset´en a G+ j´ ∗ utt egy a j´ arhat´ o elemi komponensek csal´ adjai a → r´eszbenrendez´essel egy¨ O(|E(G)|) fut´ asi idej˝ u algoritmussal meghat´ arozhat´ oak.

Szoliton automat´ ak dekompoz´ıci´ oja A szoliton ´aramk¨ or¨ ok ´es szoliton automat´ak anal´ızis´evel kapcsolatban a k¨ovetkez˝o k´et k´erd´es vet˝odik fel term´eszetszer˝ uleg. (a) A molekulah´al´ ozat topol´ogi´ aja alapj´ an adjuk meg a rendszeren defini´ alhat´ o szoliton ´aramk¨ or egy form´alis le´ır´ as´at (p´eld´ aul verifik´ aci´o c´elj´ ab´ ol, lsd. [18]). (b) Jellemezz¨ uk a szoliton automat´ ak oszt´aly´ at. A strukt´ ur´ alis eredm´enyeink felhaszn´al´ as´aval mindk´et fenti probl´em´at az elemi szoliton automat´ ak (elemi gr´afhoz tartoz´o szoliton automat´ak) szintj´ere reduk´aljuk. Val´ oj´ aban az (a) k´erd´es is k¨onnyen megfogalmazhat´o a szoliton automat´ak nyelv´en: adjunk egy m´ odszert, amely a G gr´afhoz rendelt szoliton automata egy form´alis le´ır´ as´at adja. El˝ osz¨or a fenti k´erd´es legk´ezenfekv˝obb megk¨ozel´ıt´es´et t´argyaljuk. Automata Konstrukci´ os Probl´ ema (Automaton Construction af eset´en konstru´ aljuk meg a gr´ afhoz Problem – ACP): Adott G szoliton gr´ rendelt automat´ at. A feladat megold´asa ´erdek´eben meg kell hat´aroznunk az ´allapothalmazt, valamint az ´atmenetf¨ uggv´enyt. Az ´allapotok halmaza a teljes p´aros´ıt´ asokkal rendelkez˝o p´aros gr´afokra a [24] cikkben kidolgozott m´ odszer egyszer˝ u kiterjeszt´es´evel megkonstru´alhat´ o. Az ´atmenetf¨ uggv´eny meghat´aroz´asa ´erdek´eben a szoliton ´atmeneteket altern´al´ o vonalak seg´ıts´eg´evel jellemezt¨ uk ([4]). Ezen karakteriz´ aci´o eredm´enyek´ent egy olyan elj´ar´ ast kaptunk, amely tetsz˝oleges k´et ´allapot oz¨ott eset´en O(|V (G+ )| · |E(G+ )|) id˝oben eld¨onti, hogy van-e a k´et ´allapot k¨ ´atmenet. Az elmondottak alapj´an a k¨ovetkez˝o eredm´eny ad´odik ACP kom-

8 plexit´as´ara. olje 7. T´ etel. Legyen G egy szoliton gr´ af, n = |V (G+ )|, m = |E(G+ )| ´es jel¨ + 2 allapotainak a sz´ am´ at. Ekkor ACP megoldhat´ o O(k · n · m) id˝ oben. kaG ´ Dassow ´es J¨ urgensen a [12] munk´ ajukban fontos speci´ alis esetk´ent az egy k¨ uls˝ o cs´ uccsal rendelkez˝o determinisztikus szoliton automat´ak oszt´aly´ at jellemezt´ek. A k¨ovetkez˝oekben ´altal´ anos´ıtjuk eredm´eny¨ uket nemdeterminisztikus szoliton automat´akra. Defin´ıci´ o. Legyen M a G szoliton gr´af egy ´allapota ´es v a G-nek egy k¨ uls˝ o cs´ ucsa. Egy β M -altern´ al´ o v-k¨ or´ ut egy olyan M -altern´ al´ o vonal, amely vuls˝ o M -altern´ al´ ou ´tb´ ol valamint egy βc p´ aros hosssz´ u b˝ol indul ´es egy βh k¨ M -altern´al´ o k¨orb˝ ol tev˝odik ¨ossze. Egy α M -altern´ al´ o kett˝ os v-k¨ or´ ut alatt at ´ertj¨ uk, melyre fenn´ all, hogy M -altern´al´ o v-k¨orutak egy olyan (α1 , α2 ) p´arj´ 1 E(αh ) ∩ E(αc2 ) = ∅, E(αh2 ) ∩ E(αc1 ) = ∅, valamint vagy αc1 = αc2 vagy V (αc1 ) ∩ V (αc2 ) = ∅. Defin´ıci´ o. Legyen A = (S, X, δ) egy olyan automata, melynek a´b´ec´eje egyetlen jelb˝ol ´all, azaz X = {x}. Azt mondjuk, hogy A egy teljes (szemi-teljes) automata, ha b´ armely s ∈ S eset´en δ(s, x) = S (illetve, δ(s, x) = S \ {s} felt´eve, hogy |S| > 1) ´all fenn. 8. T´ etel Legyen G egy szoliton gr´ af, mely egyetlen v k¨ uls˝ o cs´ ucsot tartalmaz. Ekkor A(G) vagy egy teljes vagy egy szemi-teljes automata. Tov´ abb´ a + os v-k¨ orutat nem A(G) szemi-teljes akkor ´es csakis akkor ha G egy kett˝ tartalmaz´ o p´ aros gr´ af. A fenti eredm´eny fontos szerepet j´atszik a szoliton automat´ak elemi dekom´gynevezett poz´ıci´oj´ aban, melyet egy speci´alis α0ε -szorzat ([15], [16], [23]), az u kanonikus szorzat seg´ıts´eg´evel adunk meg. Ezen szorzat form´alis defin´ıci´ oja azonban tov´ abbi el˝ok´esz¨ uleteket ig´enyel. Defin´ıci´ o. Legyen A(G) = (S(G+ ), X ×X, δ) egy szoliton automata. Ekkor A(G) kiterjeszt´ese alatt azt az Ae (G) = (S(G+ ), X × X, δe ) automat´at ´ertj¨ uk, ahol G b´ armely M ´allapota ´es a k¨ uls˝ o cs´ ucsok b´armely (v, w) ∈ X×X rendezett p´arja eset´en:


δe (M, (v, w)) =

δ(M, (v, w)), ha v = w δ(M, (v, w)) ∪ {M }, egy´ebk´ent

Defin´ıci´ o. Legyen Xi egy ´ab´ec´e ´es Ai = (Si , Xi × Xi , δi ) egy automata osen izomorfak ha l´etezik i = 1, 2 eset´en. Azt mondjuk, hogy A1 ´es A2 er˝ bijekt´ıv lek´epez´esek egy olyan ψ = (ψS , ψX ) p´arja, hogy ψS : S1 → S2 ´es

9 os´eget minden s ∈ S1 ´es minden ψX : X1 → X2 kiel´eg´ıtik az al´abbi egyenl˝ x, x ∈ X1 eset´en: {ψS (s ) | s ∈ δ1 (s, (x, x ))} = δ2 (ψS (s), (ψX (x), ψX (x ))) Azt mondjuk, hogy A1 ´es A2 k¨oz¨ott egy szoliton izomorfizmus ´all fenn, ha i = 1, 2 eset´en l´etezik egy A(Gi ) szoliton automata, hogy Ai er˝osen abb´ a Ae (G1 ) er˝osen izomorf Ae (G2 )-vel. izomorf A(Gi )-vel, tov´ A fenti fogalmak felhaszn´ al´ as´aval a k¨ovetkez˝ok´epp defini´ aljuk a sz¨ uks´eges automata szorzatot. Defin´ıci´ o. Tekints¨ uk a G1 , . . . , Gn (n ∈ N ) szoliton gr´afokat ´es minden egyes i ∈ [n] eset´en jel¨olje Ai = (Si , Xi × Xi , δ i ) a Gi -hez tarugv´ennyel ´es az toz´o szoliton automat´at, azaz Ai = A(Gi ) a δ i ´atmenetf¨ + abb´ a legyen L = {An+1 , . . . , Am } Si = S(Gi ) ´allapothalmazzal. Tov´ (n ≤ m) (nem sz¨ uks´egszer˝ uen szoliton) automat´ak egy rendszere, jel¨olje ugg˝ os´egnek Aj = (Sj , Xj , δ j ) (n + 1 ≤ j ≤ m), ´es legyen τ egy kanonikus f¨ nevezett lek´epez´es L-b˝ ol a G1 , . . . , Gn kanonikus oszt´alyai ´altal alkotott halol az L-be t¨ort´en˝ o maz hatv´anyhalmaz´ aba. Ekkor egy a Q = {A1 , . . . , An }-b´ τ -hoz rendelt kanonikus szorzat alatt a Ae (G1 ), . . . , Ae (Gn ), An+1 , . . . , Am automat´ak egy olyan φ = (φ1 , . . . φm ) visszacsatol´asi f¨ uggv´enyhez ´es X × X ´ab´ec´ehez tartoz´o szorzat´at ´ertj¨ uk, amelynek eredm´enyek´eppen el˝o´all´ oA= (S, X × X, δ) automat´ara a k¨ovetkez¨ok ´erv´enyesek. uls˝ o cs´ ucsainak (a) X = X1 . . .Xn , ahol minden i ∈ [n] eset´en Xi a Gi k¨ a halmaz´at jel¨oli (b) S = S1 × . . . × Sm (c) Minden i ∈ [m] eset´en φi egy olyan lek´epez´es, melyre a k¨ovetkez˝ok ´allnak fenn: (c1) Ha i ≤ n, akkor φi : X × X → (Xi × Xi ) ∪ {ε}, ´es b´armely v, w ∈ X eset´en,


φi ((v, w)) =

(v, w), ha v, w ∈ Xi ε, egy´ebk´ent

(c2) Ha n + 1 ≤ i ≤ m, akkor φi : S1 × . . . × Sn × (X × X) → (Xi × Xi ) ∪ {ε}, ´es minden M1 ∈ S1 , . . . , Mn ∈ Sn , valamint v, w ∈ X eset´en, felt´eve hogy v ∈ Xk ´es w ∈ Xl valamely k, l ∈ [n]-re, φi (M1 , . . . , Mn , (v, w)) = ε

10 akkor ´es csakis akkor ´all fenn, ha a k¨ ovetkez˝o felt´etelek valamelyike teljes¨ ul: (c2/i) τ (Ai ) ∩ PGk (Mk , v) = ∅, ahol PGk (Mk , v) jel¨oli Gk azon kanonikus oszt´alyainak a halmaz´ at, melyek minden cs´ ucsa allapotban. el´erhet˝o v-b˝ol az Mk ´ (c2/ii) k = l (c2/iii) k = l, v = w ´es δ k (Mk , (v, w)) = {Mk } (d) B´ armely x, x ∈ X ´es (s1 , . . . , sm ) ∈ S eset´en, δ((s1 , . . . , sm ), (x, x )) = δe1 (s1 , φ1 ((x, x ))) × . . . × δen (sn , φn ((x, x )))× × δ n+1 (sn+1 , φn+1 (s1 , . . . , sn , (x, x ))) × . . . × δ m (sm , φm (s1 , . . . , sn , (x, x ))) Tov´ abb´ a, ha n = m (azaz L = ∅), akkor A(G1 ), . . . , A(Gn ) diszjunkt szorzat´ ar´ ol besz´el¨ unk. Intuit´ıvan, egy kanonikus szorzat egy olyan speci´ alis α0ε -szorzat, ahol az automat´ak k´et szinten helyezkednek el. Az als´o szinten elhelyezked˝o (nem felt´etlen¨ ul szoliton) automat´ ak a fels˝o szinten elhelyezked˝o szoliton automat´akhoz azok kanonikus oszt´alyain kereszt¨ ul kapcsol´odnak. Ezen kapcsol´od´ as egy u ´gynevezett kanonikus f¨ ugg˝ os´eg ´altal defini´ alt, amely az als´o szinten lev˝o automat´ak halmaz´ab´ ol a fels˝o szinten elhelyezked˝o szoliton automat´ak kanonikus oszt´alyainak hatv´ anyhalmaz´ aba t¨ort´en˝o lek´epez´es. Egy als´o szinten lev˝o automat´aban akkor induk´ al´ odik egy ´atmenet, ha az inputk´ent adott cs´ ucsp´ ar els˝o komponens´eb˝ ol az automata el´erhet˝ o a kanonikus f¨ ugg˝ os´eg ´altal meghat´arozott valamely kanonikus oszt´alyon kereszt¨ ul. 9. T´ etel. ([4]) Jel¨ olje C azon automat´ ak oszt´ aly´ at, amelyek el˝ o´ allnak az elemi szoliton automat´ ak egy rendszer´eb˝ ol a teljes automat´ ak egy rendszer´ebe t¨ ort´en˝ o kanonikus szorzat eredm´enyek´ent. Ekkor a szoliton automat´ ak oszt´ alya szoliton izomorfizmus erej´eig egybeesik C-vel. asa konstrukt´ıv, azaz egy Fontos megjegyezni, hogy a fenti t´etel bizony´ıt´ m´odszert szolg´altat arra vonatkoz´ olag, hogy egy tetsz˝oleges szoliton automat´at mik´ent lehet elemi automat´ak kanonikus szorzat´ara bontani. Az eddigi eredm´enyek alkalmaz´asak´ent v´eg¨ ul visszat´er¨ unk az (a) k´erd´esben felvetett probl´em´ahoz. Automata Specifik´ aci´ os Probl´ ema (Automaton Description Problem – ADP): Tetsz˝ oleges G szoliton gr´ af eset´en adjuk meg a G-hez tartoz´ o A(G) szoliton automata egy form´ alis le´ır´ as´ at.

11 Vil´agos, hogy ACP egy megold´as´at szolg´altatja a fenti probl´em´anak, azonban az egy k¨ uls˝ o cs´ uccsal rendelkez˝o szoliton automat´ak p´eldak´ent szolg´alnak arra, hogy a form´ alis le´ır´ ashoz ak´ar az ´allapotsz´am megad´asa is elegend˝o lehet, amennyiben az illet˝o gr´af bels˝o strukt´ ur´ aj´ at ismerj¨ uk. A [4] dolgozatban megmutattuk, hogy a fenti probl´em´ara b´armely szoliton gr´afban alkalmazhat´ o egy strukt´ ur´ alis redukci´ o. Ezen eredm´eny tov´ abbfejleszt´esek´ent a disszert´aci´oban kidolgoztuk az u ´gynevezett Elemi Strukt´ ur´ alis K´ odol´ ast ´es megmutattuk, hogy a strukt´ ur´ alis k´od hat´ekonyan ki is sz´am´ıthat´ o. Egy ilyen k´ odol´ as a k¨ovetkez˝okb˝ ol tev˝odik ¨ossze: a gr´af k¨ uls˝ o elemi komponensei kieg´esz´ıtve bizonyos szab´alyok alapj´ an hozz´aadott tiltott ´elekkel, az u ´gynevezett ´ athidal´ o cs´ ucsok halmaza (cs´ ucsok, amelyek k¨ uls˝ o elemi komponensben fekszenek ´es szomsz´edosak valamely bels˝o komuls˝ o komponensek kanonikus oszt´alyoz´ asa, ponenshez tartoz´o cs´ uccsal), a k¨ minden egyes bels˝o komponensre annak a teljes automat´ anak az azonos´ıt´ oja, amelynek ´allapotsz´ama megegyezik az adott komponens ´allapotsz´am´aval, ´es egy rel´aci´o a fenti teljes-automata k´odok ´es a kanonikus oszt´alyok ´altal alkotott halmaz hatv´anyhalmaza k¨oz¨ott. Ezen strukt´ ura ekvivalens az eredeti automat´aval az ADP-re vonatkoz´ olag, de egy alacsonyabb komplexit´ ast biztos´ıt. A strukt´ ur´ alis k´odol´ as form´alis defin´ıci´ oj´ at helysz˝ uke miatt elhagyjuk, de ismertetj¨ uk az ADP-re vonatkoz´ o algoritmikus k¨ ovetkezm´eny´et. 10. T´ etel. Legyen G egy szoliton gr´ af, melynek minden k¨ uls˝ o elemi komponense polinomi´ alis sz´ am´ u´ allapottal rendelkezik, tov´ abb´ a minden el´erhet˝ o C bels˝ o elemi komponense eset´en polinomi´ alis id˝ oben meghat´ arozhat´ o C ´ allapotainak a sz´ ama. Ekkor ADP polinomi´ alis id˝ oben megoldhat´ o G-re.

Determinisztikus szoliton automat´ ak Komplex rendszerek anal´ızise eset´en mindig egy k¨ozponti k´erd´es, hogy meghat´arozzuk a rendszer azon jellemz˝oit, amelyek determinisztikuss´a teszik. A szoliton automat´ak bels˝o strukt´ ur´ aj´ at a 9. T´etel karakteriz´alja, ´ıgy a determinisztikusss´ag fogalma term´eszetes m´odon kiterjeszthet˝o: egy szoliton automata parci´ alisan determinisztikus, ha az alapobjektum´ at k´epez˝o gr´af b´armely k¨ uls˝ o elemi komponense egy determinisztikus szoliton gr´afot alkot. Annak ´erdek´eben, hogy a determinisztikus ´es parci´alisan determinisztikus automat´akra vonatkoz´ o gr´afstrukt´ ura egyszer˝ ubb le´ır´ as´ahoz jussunk, egy redukci´ os m´odszert defini´alunk a gr´ afokon. Defin´ıci´ o. A G gr´ af egy r redexe alatt olyan egym´ashoz illeszked˝o e = (u, z) ´es f = (z, v) ´eleket ´ert¨ unk, melyekre fenn´ all, hogy u ´es v k¨ ul¨ onb¨ oz˝o bels˝o

12 cs´ ucsok, valamint z foksz´ama 2. A z cs´ ucsot a redex k¨ oz´eppontj´anak, m´ıg u-t ´es v-t a redex sz´els˝ o cs´ ucsainak nevezz¨ uk. Legyen r egy redex a G gr´ afban. Az r ¨ osszeh´ uz´ asa alatt egy u ´j Gr gr´afnak a G-b˝ol val´ o olyan kontsrukci´ oj´ at ´ertj¨ uk, hogy t¨ or¨ olj¨ uk az r a k¨oz´eppontj´ at ´es a sz´els˝o cs´ ucsokat egybeolvasztjuk. A fenti redukci´ ot egy tov´ abbi m˝ uvelettel eg´esz´ıthetj¨ uk ki, az u ´gynevezett bels˝ o hurok´elek t¨orl´es´evel. Egy hurok´elt akkor nevez¨ unk bels˝onek, ha annak a cs´ ucsnak a foksz´ama, amelyre illeszkedik legal´abb 4. Defin´ıci´ o. Egy G gr´ afot reduk´ altnak nevez¨ unk, ha G nem tartalmaz sem redexet sem bels˝o hurok´elt. Egy tetsz˝oleges G gr´afon iterat´ıv m´odon v´egrehajtva a lehets´eges redukci´ okat (redex ¨osszeh´ uz´as, bels˝o hurok´elek t¨orl´ese), az elj´ar´ as v´eg´en egy r(G) reduk´ alt gr´afot kapunk. Bizony´ıthat´ o, hogy A(G) ´es A(r(G)) k¨oz¨ott l´etezik egy szoliton izomorfizmus, amely egyben er˝os izomorfizmus, ha G determinisztikus. Teh´ at a determinisztikus ´es parci´alisan determinisztikus automat´ak anal´ızise elv´egezhet˝o a reduk´ alt gr´afok seg´ıts´eg´evel. A karakteriz´aci´o kulcsa a k¨ovetkez˝o eredm´eny. Defin´ıci´ o. Egy ¨osszef¨ ugg˝ o hurok´el-mentes gr´afot ´ altal´ anos´ıtott f´ anak nevez¨ unk, ha nem tartalmaz p´ aros hossz´ u k¨ort. 11. T´ etel([7],[25]) Egy G elemi szoliton gr´ af akkor ´es csakis akkor determinisztikus, ha r(G) egy ´ altal´ anos´ıtott fa. Ezen t´etel eredm´enyek´ent a determinisztikus ´es a parci´alisan determinisztikus szoliton automat´ak oszt´alya le´ırhat´ o gesztenyecsonkok (olyan gr´afok, amelyekben a k¨ uls˝ o cs´ ucsokra illeszked˝o ´elek bels˝o v´egpontja egy k¨oz¨os v cs´ ucs, amit k´et p´arhuzamos ´el k¨ot ¨ossze a gr´af m´asik bels˝o cs´ ucs´aval) ´es ´altal´ anos´ıtott f´ak kanonikus ´es diszjunkt szorzatak´ent. 12. T´ etel. Jel¨ olje T azon szoliton automat´ ak oszt´ aly´ at, melyek alapobjektuma vagy egy ´ altal´ anos´ıtott fa, vagy egy olyan gr´ af, amely egy ´elb˝ ol ´es az egyik v´egpontj´ an egy hurok´elb˝ ol ´ all. Tov´ abb´ a jel¨ olje D azon A(G) szoliton automat´ ak oszt´ aly´ at, melyekre igaz, hogy vagy A(G) a T -hez tartozik vagy G egy gesztenyecsonk. Ekkor a k¨ ovetkez˝ ok ´ allnak fenn. (i) A parci´ alisan determinisztikus szoliton automat´ ak oszt´ alya szoliton izomorfizmus erej´eig egybeesik azon automat´ ak oszt´ aly´ aval amelyek el˝ o´ allnak T -beli automat´ ak egy rendszer´eb˝ ol a teljes automat´ ak egy rendszer´ebe t¨ ort´en˝ o kanonikus szorzat eredm´enyek´ent. (ii) A determinisztikus szoliton automat´ ak oszt´ alya er˝ os izomorfizmus

13 erej´eig egybeesik azon automat´ ak oszt´ aly´ aval amelyek el˝ o´ allnak D-beli automat´ ak diszjunkt szorzatak´ent. Az elemi determinisztikus gr´afok fenti karakteriz´ aci´oja ´es az Elemi Strukt´ ur´ alis K´odol´ as kapcs´an kifejlesztett elemi dekompoz´ıci´ os elj´ar´ as asi idej˝ u algoritmust kapunk annak eld¨ ont´es´ere, ¨otv¨ oz´es´evel egy O(n3 ) fut´ hogy egy szoliton gr´af determinisztikus-e. Ezen algoritmus h´arom r´eszb˝ol ´all: a gr´af elemi komponenseinek meghatr´aroz´as´ab´ ol, a redukci´ os m´odszerb˝ol, valamint egy elj´ar´ asb´ol, amely a reduk´ at gr´afokon a p´ aros k¨or l´etez´es´et ellen˝orzi. 13. T´ etel[25] Legyen G egy szoliton gr´ af ´es n = |V (G)|. Ekkor O(n3 ) id˝ oben eld¨ onthet˝ o, hogy G determinisztikus-e.

¨ Osszefoglal´ as Ezen disszert´aci´oban a szoliton automat´ aknak egy olyan r´eszletes strukt´ ur´ alis le´ır´ as´at adtam meg, amely a szoliton gr´afokban ´ertelmezett p´aros´ıt´ asokon alapul. Rem´enyeim szerint ezen eredm´enyeknek komoly hat´asa lesz a szoliton ´aramk¨ or¨ ok gyakorlati fejleszt´ese sor´an ´epp´ ugy, mint az alapkutat´ asok ter¨ ulet´en. Az eredm´enyek a sz´am´ıt´ astudom´ any ´es matematika t¨obb probl´em´aja kapcs´an alkalmazhat´ oak. A teljess´eg ig´enye n´elk¨ ul megeml´ıtem a p´aros´ıt´ asok strukt´ ur´ alis elm´elet´et, a h´al´ ozattervez´esi probl´em´akat, illetve az ezen modell ´altal´ anos´ıt´ asak´ent defini´ alhat´ o automat´ak vizsg´alat´ at.

Bibliography [1] A. Adamatzky, Computing in Nonlinear Media and Automata Collectives, IOP Publishing, Bristol-Philadelphia, 2001. [2] M. Bartha, E. Gomb´ as, A structure theorem for maximum internal matchings in graphs, Information Processing Letters 40 (1991), 289294. [3] M. Bartha, E. Gomb´ as, On graphs with perfect internal matchings, Acta Cybernetica 12 (1995), 111-124. [4] M. Bartha, M. Kr´esz, Elementary decomposition of soliton automata, Acta Cybernetica 14 (2000), 631-652. [5] M. Bartha, M. Kr´esz, Isolating the families of soliton graphs, Pure Mathematics and Applications 13 (2002), 49–62. [6] M. Bartha, M. Kr´esz, Structuring the elementary components of graphs having a perfect internal matching, Theoretical Computer Science 299 (2003), 179–210. [7] M. Bartha, M. Kr´esz, Deterministic soliton automata defined by elementary graphs, in Proceedings of the Kalm´ ar Workshop on Logic and Computer Science (2003) pp. 69–79. [8] M. Bartha, M. Kr´esz, Tutte type theorems in graphs having a perfect internal matching, Information Processing Letters 91 (2004), 277–284. [9] F. L. Carter, The molecular device computer: Point of departure for large scale cellular automata, Physica D 10 (1984), 175–194. [10] J. Dassow, H. J¨ urgensen, Soliton automata, J. Comput. System Sci. 40 (1990), 154-181.

14

BIBLIOGRAPHY

15

[11] J. Dassow, H. J¨ urgensen, Soliton automata with a single exterior node, Theoretical Computer Science 84 (1991), 281–292. [12] J. Dassow, H. J¨ urgensen, Soliton automata with at most one cycle, Journal of Computer and System Sciences 46 (1993), 155–197. [13] J. Dassow, H. J¨ urgensen, The transition monoids of soliton trees, Research Report # 331, Department of Computer Science, The University of Western Ontario, London, Canada, 1992. [14] J. Edmonds, Paths, trees and flowers, Canad. J. Math. 17 (1965), 449– 467. ´ [15] Z. Esik, J. Vir´ agh, On products of automata with identity, Acta Cybernetica 7 (1986), 299–311. [16] F. G´ecseg, Products of Automata, Akademie-Verlag, Berlin, 1986. [17] F. G´ecseg, H. J¨ urgensen, Automata represented by products of soliton automata, Theoretical Computer Science 74 (1990), 163–181. [18] M. P. Groves, Towards verification of soliton circuits, in Molecular Electronic Devices (F. L. Carter, R. E. Siatkowski, H. Wohltjen Ed.), North-Holland, Amsterdam, 1988, pp. 287–302. [19] M. P. Groves, C. F. Carvalho, C. D. Marlin, and R. H. Prager, Using Soliton Circuits to Build Molecular Memories, Australian Computer Science Communications 15 (1993) pp. 37–45. [20] M. P. Groves, C. D. Marlin, Using Soliton Circuits to Build Molecular Computers, Australian Computer Science Communications 17 (1995) pp. 188–193. [21] M. P. Groves, C. F. Carvalho, and R. H. Prager, Switching the polyacetylene soliton, Materials Science and Engineering C3 (1995) pp. 181–185. [22] M. P. Groves, Soliton Circuit Design Using Molecular Gate Arrays, in Proceedings of the 20th Australasian Computer Science Conference (1997) pp. 245–252. [23] B. Imreh, M. Ito, On αi -product of nondeterministic automata, Algebra Colloquium 4 (1997), 195–202.

BIBLIOGRAPHY

16

[24] A. Itai, M. Rodeh, S. Tanimoto, Some matching problems for bipartite graphs, Journal of the ACM 25 (1978), 517–525. [25] M. Kr´esz, Alternating cycles in soliton graphs, WSEAS Transactions on Mathematics 1 (2002), 165–170. [26] L. Lov´ asz, M. D. Plummer, Matching Theory, North Holland, Amsterdam, 1986. [27] T. Sienko, A. Adamatzky, N. Rambidi, and M. Conrad (Ed.), Molecular Computing, The MIT Press, London, 2003. [28] D. M. Taylor, Molecular nanostructures and their electrical probing, Thin Solid Films 331 (1998), 1–7. [29] W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111. [30] Y. M. Yin, X. Q. Lin, Progress on molecular computer, Progress in Chemistry 13 (2001), 337–342.

Irodalomjegyz´ ek

17