Regularitást megőrző függvényekről

Pontos bibliográfiai adatok: Dexter Kozen. On Regularity-Preserving Functions Technical Report of Cornell University, TR95-1559.

Rövid cím: Regularitást megőrző függvényekről.

Ismert, hogy ha A egy reguláris nyelv, akkor az

A_{n} = {x | ∃y : l(y) = l(x) és xy ∈ A}

nyelv szintén reguláris. Valamivel komplikáltabb a bizonyítása annak, hogy

A_{n^{2}} = {x | ∃y : l(y) = l(x)^{2} és xy ∈ A},
A_{2^{n}} = {x | ∃y : l(y) = 2^{l(x)} és xy ∈ A}, és
A_{2^{2^{n}}} = {x | ∃y : l(y) = 2^{2^{l(x)}} és xy ∈ A}

nyelvek valamennyien regulárisok. A cikk kétféle módon is meghatározza azon függvények osztályát, melyek a fenti értelemben „megőrzik a regularitást”, azaz meghatározza az olyan f függvények osztályát, melyre minden reguláris A nyelvből a fenti séma szerint készített A_{f} nyelv reguláris marad.

Nyelvek generálása kétfajta zárójelpár segítségével

Pontos bibliográfiai adatok: Viliam Geffert. How to generate languages using only two pairs of parentheses. EIK: Journal of Information Processing and Cybernetics EIK (formerly Elektronische Informationsverarbeitung und Kybernetik), 27, 1991.

Rövid cím: Geffert normálforma.

A szerző két jól használható normálformát ad a 0. típusú nyelvtanokra.

Tétel. Minden G nulladik típusú nyelvtanhoz megadható egy vele ekvivalens G′ nyelvtan, melynek idő– és térbonyolultsága aszimptotikusan egyenlő a G nyelvtanéval, mindössze 5 nemterminális szimbólumot használ (ezek: S′, (,), [,]), szabályai kettő kivételével környezet–függetlenek. (A két kivétel: () → ϵ, és [] → ϵ.)

Tétel. Minden G nulladik típusú nyelvtanhoz megadható egy vele ekvivalens G′ nyelvtan, melynek idő– és térbonyolultsága aszimptotikusan egyenlő a G nyelvtanéval, mindössze 5 nemterminális szimbólumot használ (ezek: S′, X, A, B, C), szabályai egy kivételével környezet–függetlenek. (A kivétel: ABC → ϵ.)

Sejtautomaták

Pontos bibliográfiai adatok: Jozef Gruska. Foundations of Computing. International Thomson Computer Press, 1997

Rövid cím: Sejtautomaták.

Az ötvenes években a kutatókat foglalkoztató egyik legizgalmasabb kérdés az volt, hogy képesek–e gépek önmaguk reprodukálására. Egyfajta választ erre a kérdésre Neumann János adott, aki megalkotta 1953–ban a sejtautomatákat, biológiai motivációk alapján. Ezzel megmutatta, hogy léteznek ön–reprodukáló gépek. A sejtautomaták később a párhuzamos számítógépek egy modelljének matematikai alapját is képezték.

A sejtautomaták olyan véges állapotú automatáknak valamilyen d–dimenziós elrendezésű, minden irányban végtelen hálózata, melyben minden automata azonos működésű, és az állapot–átmenetek csak az adott automata „szomszédjainak” állapotától függenek. A hálózat párhuzamosan működik, szinkronizáltan és diszkrét lépésekben.

A könyvrészlet pontosan definiálja a sejtautomaták fogalmát, példákat ad rá. Részletesebben foglalkozik két speciális esettel: a sokak által ismert életjátékkal és a lövész–osztagok szinkronizációs problémájával. Végül megmutatja azt a rendkívül fontos elméleleti tételt, hogy a sejtautomaták és a Turing–gépek képesek egymás hatékony szimulációjára, illetve bevezeti a reverzibilis sejtautomaták fogalmát. A fejezetet feladatok zárják, néhány érdekesebb feladat megoldásának ismertetése hozzátartozik a dolgozat bemutatásához.

Ismételt GSM leképezések: egy összeomló hierarchia

Pontos bibliográfiai adatok: Vincenzo Manca, Carlos Martin-Vide és Gheorghe Păun: Iterated GSM Mappings: A Collapsing Hierarchy. In: Jewels Are Forever, pp. 182-193, Springer-Verlag, New-York, Salomaa A., Maurer H., Paun G. editors 1999

Rövid cím: Ismételt GSM leképezések.

GSM leképezések ismételt alkalmazásának segítségével definiálhatunk különböző nyelvcsaládokat. A felhasznált GSM-ben levő állapotok száma szerint végtelen sok nyelvcsaládot kapunk. Ezek a nyelvcsaládok természetesen hierarchikusan egyre bővülnek, de a cikk belátja, hogy 4 állapotú GSM segítségével már tetszőleges rekurzívan felsorolható nyelvet megkaphatunk, így a hierarchia összeomlik. A dolgozat vizsgálja még az egyes nyelvosztályok nagyságát a Chomsky–osztályokhoz és a különböző Lindenmayer nyelvosztályokhoz képest.

A nyelvdefiniálásnak ezen modellje a molekuláris számítások tudományág egy módszerével, a faragással való számítással rokon, az eredményeknek ott lehet gyakorlati alkalmazásuk is. A determinisztikus GSM leképezések ismételt alkalmazásával megkapott nyelvek vizsgálata nem tárgya a cikknek. A terület még sok nyitott kérdést tartalmaz.

Logikai formulákkal definiálható nyelvek

Pontos bibliográfiai adatok: Arto Salomaa. Rudimentary predicates, In: Formal Languages, chapter III/12, pages 109–119. Academic Press, New York, 1973.

Rövid cím: Logikai formulák.

A formális nyelvek elméletében nyelvek definiálására a leggyakoribb eszközök vagy generálják, vagy elfogadják az adott nyelvet. A könyvrészlet egy ezektől különböző módszert mutat be: nyelvek definiálását logikai formulák segítségével. Ezek a formulák sokszor nagyon kényelmesen használhatóak, mivel a nyelvek intuitív definícióját formális leírássá fordítják. Gyakran könnyen és természetesen alkalmazhatóak adott nyelvekből újak definiálására is.

A szerző pontosan definiálja, hogy milyen típusú logikai formulákat használ nyelvek definiálására, és belátja, hogy az íly módon definiálható nyelvek osztálya megegyezik L_{0}-al.

Alternáló véges automaták

Pontos bibliográfiai adatok: Sheng Yu. Regular languages, In: Handbook of Formal Languages, Grzegorz Rozenberg and Arto Salomaa (eds). Springer, 1996.

Rövid cím: Alternáló véges automaták.

Az alternáló véges automaták (AVA) a nemdeterminisztikus véges automaták (NDVA) általánosításai. A kézikönyv-részlet megadja az AVA-k definícióját és vizsgálja néhány tulajdonságát. Megadja az AVA-k egyenletrendszerrel való reprezentálásának módszerét, bemutatja néhány normálformáját, majd megadja az AVA-k NDVA-val való szimulálásának konstrukcióját, és viszont. Végül bemutatja az AVA-k néhány speciális fajtáját.

Reguláris nyelvek bonyolultsági kérdései

Pontos bibliográfiai adatok: Sheng Yu. Regular languages, In: Handbook of Formal Languages, Grzegorz Rozenberg and Arto Salomaa (eds). Springer, 1996.

Rövid cím: Reguláris nyelvek bonyolultságai.

A reguláris nyelvek sok tulajdonságát vizsgáltuk már, de eddig a bonyolultsági kérdésekről kevés szó esett. Az összefoglaló kétféle bonyolultsági mértéket is bemutat és elemez: az állapot-bonyolultságot, illetve az idő- és térbonyolultságot. Elemzi néhány reguláris nyelvekre vonatkozó művelet állapotbonyolultságát, és megadja sok, szintén 3. típusú nyelvekre vonatkozó eldöntési probléma idő- és térbonyolultságát.

Bevezetés a formális nyelvekbe

Pontos bibliográfiai adatok: Alexandru Mateescu and Arto Salomaa. Formal Languages: an Introduction and a Synopsis, In: Handbook of Formal Languages, Grzegorz Rozenberg and Arto Salomaa (eds). Springer, 1996.

Rövid cím: Bevezetés.

A tanulmány egy formális nyelvekkel fogallkozó kézikönyv bevezető fejezete. Általános nyelvészeti bevezetővel kezdődik, majd rátér a matematikai formális nyelvekre, néhány alaptulajdonságukat részletesen vizsgálja. A fejezet a formális nyelvek elméletének távirati stílusú összefoglalásával zárul.

Az előadásnak a tanulmány 2. szakaszára kell koncentrálnia.

Kvantum automaták és kvantum nyelvtanok

Pontos bibliográfiai adatok: Christopher Moore and James P. Crutchfield. Quantum automata and quantum grammars. Theoretical Computer Science, 237 (2000) 275-306.

Rövid cím: Kvantum automaták.

A cikk bevezeti a véges automaták és a veremautomaták, valamint a regiláris és környezet-független nyelvtanok kvantumos változatait. Megmutatja néhány klasszikus tétel, pl. zártsági tételek, pumpáló lemmák stb. analógiáit. Bebizonyítja, hogy a kvantum-környezetfüggetlen nyelvek osztálya nem egyezik meg a 2. típusú nyelvek osztályával. A bevezetésben felvázolja röviden a kvantummechanika elméleti alapjait.

Kavics automaták

Pontos bibliográfiai adatok: Holger Petersen. A Census Techique for Simple Computing Devices. Technical Report of Univerität Stuttgart Fakultät Informatic, 1997/07, 1997.

Rövid cím: PA.

A tanulány egy új módszert mutat arra, hogy hogyan lehet többszámlálójú gépeket kavics-automatákkal gazdaságosan, azaz kevés kavicsot használva szimulálni. Ezt az eredményt felhasználva megmutatja, hogy a korábban javasolt nyelv-halmazok nem alkalmasak annak megmutatására, hogy a kavicsautomaták hatóereje a felhasznált kavicsok számával vég nélkül növekszik.

Sztohasztikus időzített automatákról

Pontos bibliográfiai adatok: Danièle Beauquier. On probabilistic timed automata. Theoretical Computer Science, 292 (2003), 65-84.

Rövid cím: PTA.

A cikk javasolja a szokásos nemdeterminisztikus időzített automaták általánosítását a sztohasztikus időzített automaták modelljének megadásával. Rámutat az így kapott modell és a Markov döntési folyamatok közötti összefüggésekre.