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

Pontos bibliográfiai adatok:
Dexter Kozen. On Regularity-Preserving Functions

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 A_f nyelv reguláris marad.

Poli-karcsú nyelvek osztályozása

Pontos bibliográfiai adatok:
Lucian Ilie, Grzegorz Rozenberg és Arto Salomaa. Chomsky-Schützenberger-Type Representations of Poly-Slender Context-Free Languages. Technical Report, Turku Centre for Computer Science, Finland, Number TUCS-TR-242, March 1, 1999.

Rövid cím: Poli-karcsú nyelvek osztályozása.

Jelölje #_L(n) az n betűből álló szavak számát az L nyelvben. Azt mondjuk, hogy L karcsú (slender), ha #_L(n) Ł c valamilyen c egészre. L k-poli-karcsú, ha #_L(n) Î O(n^k), és L poli-karcsú, ha létezik olyan k egész szám, melyre #_L(n) Î O(n^k). A cikk megmutatja, hogy a környezetfüggetlen k-poli-karcsú nyelvek struktúrájának alapja megegyezik a magasabbrendű helyes zárójelezéseket tartalmazó Dyck-nyelvekével, íly módon karakterizálva a környezetfüggetlen k-poli-karcsú nyelveket.

Rekurzívan felsorolható nyelvek reprezentálása belső szövegkörnyezet nyelvekkel

Pontos bibliográfiai adatok:
Andrzej Ehrenfeucht, Gheorghe Paun s Grzegorz Rozenberg: On representing recursively enumerable languages by internal contextual languages. Theoretical Computer Science, Vol. 205, Number 1-2, pp. 61-83, 28 September 1998.

Rövid cím: ICL nyelvek.

A belső szövegkörnyezet nyelvtan egy olyan hármas, ami egy abc-ből, axiómák véges halmazából és (x,u$v) alakú szabályok véges halmazából áll, ahol x, u és v szavak, $ pedig egy speciális jel. Egy ilyen szabályt alkalmazhatunk egy y szóra, ha az tartalmazza az x részszót, ekkor x egy előfordulását y-ban uxv-ra cseréljük. Más szóval körülvesszük az x szót az (u,v) környezettel. A nyelvtan által generált nyelvbe a tetszőleges axiómából, véges sok szabály alkalmazásával kapott szavak összessége tartozik. Az ilyen nyelvtanok által definiálható nyelvek osztályát nevezzük belső szövegkörnyezet nyelveknek, jelölése: ICL.

A cikk megmutatja, hogy az ICL nyelvek tartalmazzák a reguláris nyelveket, részei a környezet-függő nyelveknek, és nem összehasonlíthatóak a környezet-független és a lineáris nyelvekkel. Fő eredményként pedig bebizonyítja, hogy tetszőleges rekurzivan felsorolható nyelv előáll egy ICL nyelvből bizonyos műveletek segítségével. Végül röviden megvizsgálja az egyoldalú ICL nyelveket, mikor is a nyelvtan minden (x,u$v) szabályára u = e, vagy v = e.

Egy ,,kicserélési lemma'' környezet-független nyelvekre

Pontos bibliográfiai adatok:
William Ogden, Rockford J. Ross, and Karl Winklmann. An ``interchange lemma'' for context-free languages. SIAM Journal on Computing, 14(2):410-415, May 1985.

Rövid cím: Kicserélési lemma.

A cikk egy új szükséges feltételt ad környezet-független nyelvekre, majd példát is ad az alkalmazására: a lemma segítségével belátja, hogy nem környezet-független egy olyan nyelvről, amely sokáig ellenállt minden hasonló bizonyítási kísérletnek.

Tétel. Legyen L egy T abc-jű környezet-független nyelv. Ekkor létezik olyan c > 0 konstans, hogy minden n ł 2 egészre, minden Q Í L ÇTⁿ halmazra és minden olyan m egészre, melyre n ł m ł 2 létezik k ł |Q|/(cn²) egész és z₁,Ľ, z_k Î Q szavak a következő tulajdonságokkal:

1. z_i = w_ix_iy_i, i = 1,Ľ, k,
2. |w₁| = |w₂| = Ľ = |w_k|,
3. |y₁| = |y₂| = Ľ = |y_k|,
4. m ł |x₁| = |x₂| = Ľ = |x_k| > m/2, és
5. w_ix_jy_i Î L minden i,j Î {1,2,Ľ, k} esetén.

A bizonyítás Chomsky normálformában levő nyelvtanokhoz tartozó levezetési fák levelei számlálásának segítségével történik.

A cikk az alkalmazásra is példát ad: megmutatja, hogy a ,,dadogó'' szavak (azaz az xyyz alakú szavak, ahol y nem üres) nyelve hárombetűs abc felett nem környezet-független.

Szavak kombinatorikus tulajdonságai és a Chomsky osztályok kapcsolata

Pontos bibliográfiai adatok:
Dömösi Pál et al. Some combinatorial properties of words, and the Chomsky hierarchy. In Proc. Internat. Conf. ``Words, Languages and Combinatorics, II'', Kyoto, Japan; eds.: M. Ito and H. Jürgensen, pages 105-123. Singapore: World Scientific, 1992.

Rövid cím: Kombinatorikus tulajdonságok.

Jelöljük Q-val a primitív szavak nyelvét, azaz azokat a szavakat, amelyek nem állnak elő más szó hatványaként. (Formálisan Q = T⁺\{w^m | w Î T^*, m ł 2}, ahol T egy legalább kétbetűs abc.) Sokat kutatott téma, hogy vajon Q környezet-független-e, a sejtés az, hogy nem. Jelen cikk nem dönti el a kérdést, de belátja, hogy Q teljesít három olyan feltételt, az Ogden, az erős Bader-Moura és a Sokolowsky feltételt, amelyet minden környezet-független nyelv teljesít. A cikk egy negyedik feltételt is vizsgál, ami szükséges feltétele minden környezet-független nyelvnek, a Parikh szemilinearitást. Megmutatja, hogy QÇ(a^*b)ⁿ (ahol n ł 1 egész) Parikh szemilineáris, tehát ez a támadási kísérlet is kudarcot vall. A dolgozat utolsó része általánosan vizsgál bizonyos nyelvi tulajdonságokat, különös tekintettel azok eldönthetőségére és elhelyezkedésükre a Kleene féle aritmetikai hierarchiában.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a Ogden feltételt, ha létezik olyan n ł 2 egész, melyre z Î L esetén, ha legalább n+1 pozíciót z-ben kitüntetettnek tekintünk, akkor z felbontható z = uvwxy alakban, ahol teljesülnek a következők:

1. vagy u, v és w, vagy w, x és y mindegyike tartalmaz kitüntetett pozíciót,
2. vwx legfeljebb n kitüntetett pozíciót tartalmaz,
3. minden m ł 0 számra uv^mwx^my Î L.

Tétel. Minden környezet-független nyelv teljesíti az Ogden feltételt.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a Sokolowsky feltételt, ha minden Y Í T^*, |Y| ł 2, és minden u₁, u₂, u₃ Î T^* esetén, ha {u₁xu₂xu₃ | x Î Y⁺} Í L, akkor létezik olyan x˘,x˘˘ Î Y⁺, x˘ ą x˘˘, melyre u₁x˘u₂x˘˘u₃ Î L.

Tétel. Minden környezet-független nyelv teljesíti a Sokolowsky feltételt.

Környezet-független nyelvekre adott kicserélési és pumpáló lemmák

Pontos bibliográfiai adatok:
R. Boonyavatana and G. Slutzki. The interchange or pump (DI)lemmas for context-free languages. Theoretical Computer Science, 56(3):321-338, March 1988.

Rövid cím: Feltételek összehasonlítása.

A cikk összehasonlítja a kicserélési lemmát különböző pumpáló lemmákkal: a Bar-Hillel félével, Ogdenével, ennek általánosított változatával, a fentiek lineáris változatával, valamint a Sokolowsky féle feltételekkel. Ezen felül definiál egy kicserélési feltételt lineáris környezet-független nyelvekre, és összehasonlítja a többi feltétellel. Az eredmények megmutatják, hogy a kicserélési feltételek nem összehasonlíthatóak a pumpáló feltételekkel és a kiterjesztett Sokolowsky feltétellel, de határozottan erősebbek a Sokolowsky feltételnél.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a lineáris kicserélési feltételt, ha létezik olyan c > 0 konstans, hogy minden n ł m ł 2 egészekre, és minden Q Í L ÇTⁿ halmazra létezik R Í Q a következő tulajdonságokkal:

1. |R| ł |Q|/(cn), és
2. valamilyen i ł 0 számra {xwy | $u,v,z Î T^* : |x| = |u| = i, |w| = |z| = m, xzy,uwv Î R} Í LÇTⁿ.

Definíció. Azt mondjuk, hogy egy R Í T^*×T^* reláció nem korlátos, ha minden m számra léteznek olyan x,y Î T^* szavak, melyre |x|,|y| ł m, és R(x,y) fennáll.

Definíció. x,y Î T^* esetén x < y azt jelenti, hogy x-et úgy kaphatjuk y-ból, hogy néhány betűjét kitöröljük. Ha a törölt szimbólumok y utolsó (első) m szimbóluma közül kerülnek ki, azt így jelöljük: x < ^my (x  ^m < y). Szavak párjaira definiáljuk a következő relációt:

(x˘,y˘) < m (x,y) Ű (x˘ < xŮy˘ = y) Ú(x˘ = xŮy˘ < y) Ú(x˘ < m x Ůy˘ m < y).

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a kiterjesztett Sokolowsky feltételt, ha minden u₁,u₂,u₃ Î T^* szóra és minden R Í T^*×T^* nem korlátos relációra, ha {u₁xu₂yu₃ | R(x,y)} Í L, akkor létezik olyan m egész, hogy minden x,y Î T^* esetén

|x|,|y| > m Ů R(x,y)\implies$x˘,y˘: (x˘,y˘) < m (x,y) Ů u1x˘u2y˘u3 Î L.

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

Az eldönthetőség és az el nem dönthetőség határmezsgyéjén I.

Rövid cím: Eldönthetőség I..

A tanulmány pontosan definálja az eldönthetőség és az el nem dönthetőség fogalmát, majd áttekintést ad a lehető legélesebb határokról, ami az eldőnthető problémák és a hozzájuk tartozó eldönthetetlen problémák között fekszenek. A diszkrét számítások széles köréből veszi a problémákat, az érintett modellek: diofantoszi egyenletek, a szóprobléma, Post-féle rendszerek, molekuláris számítások, regiszter-gépek, neurális hálózatok, sejtautomaták, síklefedések, síkbeli Turing-gépek. Ezek után rátér a klasszikus Turing gépek elemzésére, és egy példával fejezi be a problémák bemutatását: az ún. 3x + 1 problémát elemzi.

Az első (I.) részhez az első két fejezet: a bevezetés és a klasszikus Turing gépen kívüli modellek tartoznak.

Az eldönthetőség és az el nem dönthetőség határmezsgyéjén II.

Rövid cím: Eldönthetőség II..

A tanulmány pontosan definálja az eldönthetőség és az el nem dönthetőség fogalmát, majd áttekintést ad a lehető legélesebb határokról, ami az eldőnthető problémák és a hozzájuk tartozó eldönthetetlen problémák között fekszenek. A diszkrét számítások széles köréből veszi a problémákat, az érintett modellek: diofantoszi egyenletek, a szóprobléma, Post-féle rendszerek, molekuláris számítások, regiszter-gépek, neurális hálózatok, sejtautomaták, síklefedések, síkbeli Turing-gépek. Ezek után rátér a klasszikus Turing gépek elemzésére, és egy példával fejezi be a problémák bemutatását: az ún. 3x + 1 problémát elemzi.

A második részhez a 3, 4, 5 fejezetek tartoznak: a klasszikus Turing gépek elemzése, a 3 x + 1 probléma és a befejezés.

Kooperáló nyelvtan-rendszerek I.

Rövid cím: Nyelvtan-rendszerek I.

A klasszikus formális nyelvi elméletek olyan eszközökkel (pl. automata, nyelvtan) dolgoznak, melyek elfogadnak, vagy generálnak egy-egy nyelvet. Ez a megközelítés a hagyományos olyan területeken, mint pl. természetes nyelvek elemzése, programozási nyelvek fordítása. Az utóbbi időkben viszont egyre elterjedtebbek azok a megközelítési módok, amikben nem egy eszköz old meg egy feladatot, hanem több, viszonylag egyszerűbb eszköz együttműködve dolgozik a probléma megoldásán. A könyvrészlet a nyelvtanok fogalmát terjeszti ki ebben az értelemben: definálja a kooperáló nyelvtan-rendszerek fogalmát és megvizsgálja azok tulajdonságait.

Az első (I.) részhez a 3.1 és a 3.2 fejezetek tartoznak.

Definíció. CD grammatika rendszer alatt a következő n+2-est értjük:

G = (T,G1,...,Gn,S), ahol

• G_i = (N_i,T_i,P_i) (1 Ł i Ł n) szokásos, axióma nélüli környezet-független grammatikák, N_i a nemterminálisok halmaza, T_i a terminálisoké, P_i a szabályhalmaz,
• T Í Č_{i = 1}ⁿ T_i ,
• S Î Č_{i = 1}ⁿ N_i = N .

Kooperáló nyelvtan-rendszerek II.

Rövid cím: Nyelvtan-rendszerek II.

A klasszikus formális nyelvi elméletek olyan eszközökkel (pl. automata, nyelvtan) dolgoznak, melyek elfogadnak, vagy generálnak egy-egy nyelvet. Ez a megközelítés a hagyományos olyan területeken, mint pl. természetes nyelvek elemzése, programozási nyelvek fordítása. Az utóbbi időkben viszont egyre elterjedtebbek azok a megközelítési módok, amikben nem egy eszköz old meg egy feladatot, hanem több, viszonylag egyszerűbb eszköz együttműködve dolgozik a probléma megoldásán. A könyvrészlet a nyelvtanok fogalmát terjeszti ki ebben az értelemben: definálja a kooperáló nyelvtan-rendszerek fogalmát és megvizsgálja azok tulajdonságait.

A második (II.) részhez a 3.3, 3.4 fejezetek, valamint a befejezés tartozik.

Definíció. CD grammatika rendszer alatt a következő n+2-est értjük:

G = (T,G1,...,Gn,S), ahol

• G_i = (N_i,T_i,P_i) (1 Ł i Ł n) szokásos, axióma nélüli környezet-független grammatikák, N_i a nemterminálisok halmaza, T_i a terminálisoké, P_i a szabályhalmaz,
• T Í Č_{i = 1}ⁿ T_i ,
• S Î Č_{i = 1}ⁿ N_i = N .

Sejtautomaták

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.

A Parikh feltétel összehasonlítása más környezetfüggetlen nyelvekre adott feltételekkel

Pontos bibliográfiai adatok:
G. Ramos-Jiménez, J. López-Munoz és R. Morales-Bueno: Comparisons of Parikh's condition to other conditions for context-free languages. Theoretical Computer Science, Vol. 202, Number 1-2, pp. 231-244, 28 July 1998.
Rövid cím: Parikh feltétel.

A Parikh-feltétel egy szükséges feltétel a környezet-független nyelvek számára. A feltétel különlegessége, hogy a szavakban levő jeleknek csak egy globális tulajdonságát vizsgálja: az egyes jelek előfordulásainak a számát.

A cikk összehasonlítja a Parikh lemmát a különböző pumpáló lemmákkal: a Bar-Hillel félével, Ogdenével, ennek általánosított változatával, a kicserélési lemmával, valamint a Sokolowsky és a Grant féle feltételekkel. Kiderül, hogy a Parikh feltétel egyik említett feltétellel sem hasonlítható össze. A bizonyítások során szép eredmények születnek a Parikh feltételt teljesítő nyelvek egyéb tulajdonságairól is.

Logikai formulákkal definiálható nyelvek

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

Lindenmayer rendszerek

Rövid cím: Lindenmayer rendszerek.

A Lindenmayer rendszerek a nyelvtanokban megszokott újraíráson alapulnak, mégis három jelentős eltérést mutatnak a nyelvtanokhoz képest. Nincsenek benne külön terminális és nyelvtani jelek, így valamennyi levezetett mondatforma generált szó is egyben. Az ebből adódó hatóerő-csökkenést némiképp ellensúlyozza, hogy nem a mondatforma egy jelét írjuk egy lépésben át, hanem egyszerre, szimultán valamennyi jelét, illetve, hogy nem kezdő jelünk (axiómánk), hanem kezdő szavunk adott. Első hallásra talán meglepő, hogy bizonyos algák növekedését olyan pontosan le lehet írni L-rendszerek segítségével, hogy az elmélet a kidolgozását is némiképp az algáknak köszönheti.

A szerző definiálja az L-rendszerek néhány fajtáját, majd példát ad rájuk. Megvizsgálja a rendszerek néhány tulajdonságát, pl. zártsági tételeket bizonyít, összehasonlítja az így definiálható nyelvosztályokat a Chomsky osztályokkal, majd ejt néhány szót az L-rendszerek ún. növekedési függvényeinek érdekességeiről.

Képnyelvek tulajdonságainak eldönthetetlenségéről

Pontos bibliográfiai adatok:
D. Robilliard et D. Simplot. Undecidability of existential properties in picture languages. Theoretical Computer Science, 233, 2 (1999), 51-74.

Rövid cím: Képnyelvek.

A cikk három módszert is leír, hogy hogy jelenthetnek meghatározott abc feletti szavak síkbeli képeket. Ilyen módon szavak nyelvéből képnyelveket kapunk. A dolgozat bevezeti a képek bizonyos geometriai tulajdonságait, és vizsgálja, hogy mikor eldönthető reguláris nyelvekről, hogy tartalmaznak-e olyan képrészletet, aminek meghatározott tulajdonsága van. Az eredmény a legtöbb esetben negatív: eldönthetetlen problémák sorát kapjuk ilyen módon.