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
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 Af nyelv reguláris marad.
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:
()®e, és []®e.)
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®e.)
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.
Pontos bibliográfiai adatok:
Vincenzo Manca, Carlos Martin-Vide és Gheorghe Paun:
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.
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 L0-al.
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.
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
állapot-bonyolultságát, és megadja sok, szintén 3. típusú nyelvekre vonatkozó
eldöntési probléma idő- és térbonyolultságát.
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.
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.
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 kavics-automaták
hatóereje a felhasznált kavicsok számával vég nélkül növekszik.
Pontos bibliográfiai adatok:
Dani\` ele 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.