Regularitást megőrző függvényekről 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}
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 Af 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: ()®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.)


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 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.


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 L0-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 á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.

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 kavics-automatá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\` 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.


File translated from TEX by TTH, version 2.64.
On 28 Jan 2003, 16:19.

BACK Vissza a Formális nyelvek és automaták szeminárium lapjára.

Utolsó módosítás: 2003.01.28 16:09
A megjegyzéseket, hibajelentéseket, jobbítási javaslatokat szívesen várja kacsa, az oldal szerzője.