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
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:
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(nk), és
L poli-karcsú, ha létezik olyan k egész szám, melyre
#L(n) Î O(nk).
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.
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.
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 ÇTn halmazra és minden
olyan m egészre, melyre n ł m ł 2 létezik
k ł |Q|/(cn2) egész és z1,Ľ, zk Î Q szavak
a következő tulajdonságokkal:
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.
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+\{wm | 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)n (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:
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 u1, u2, u3 Î T* esetén,
ha {u1xu2xu3 | x Î Y+} Í L, akkor
létezik olyan x˘,x˘˘ Î Y+, x˘ ą x˘˘, melyre
u1x˘u2x˘˘u3 Î L.
Tétel.
Minden környezet-független nyelv teljesíti a Sokolowsky feltételt.
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 ÇTn halmazra létezik
R Í Q
a következő tulajdonságokkal:
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 u1,u2,u3 Î T* szóra és minden
R Í T*×T* nem korlátos relációra,
ha {u1xu2yu3 | 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.
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: 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.
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.
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
Levezetés [x t || ( ŢGi y)], ha létezik olyan x1, ...,xk ,melyre
Generált nyelv
L(G) = {w Î T* | $w1,...,wk, i1,...,ik : S ŢGi1 w1 ŢGi2 ĽŢGik wk = w}
Elfogadási stílus
Azt mondjuk, hogy a G CD grammatika rendszer elfogadási stílusa
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
Levezetés [x t || ( ŢGi y)], ha létezik olyan x1, ...,xk ,melyre
Generált nyelv
L(G) = {w Î T* | $w1,...,wk, i1,...,ik : S ŢGi1 w1 ŢGi2 ĽŢGik wk = w}
Elfogadási stílus
Azt mondjuk, hogy a G CD grammatika rendszer elfogadási stílusa
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.
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.
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.
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.
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.