Pontos bibliográfiai adatok:
Horváth Sándor.
Ranges of polinomials are not context-free in any number system.
To appear in PuMa, June 1998.
Rövid cím: Polinomok értékkészletéről.
Tekintsünk egy egészeken értelmezett p polinomot és egy B ł 1 számot!
Definiáljunk egy L nyelvet a következőképp: a nyelv szavai
a p polinom értékkészletének nemnegatív egész elemei
B alapú számrendszerben felírva.
A cikk azzal foglalkozik, hogy az ily módon kapott L
nyelvek mely Chomsky osztályokba tartozhatnak.
Az eredmény az, hogy (a polinomra tett bizonyos megkötések mellett)
elsőfokú polinom esetén a nyelv reguláris, magasabb fokszám
esetén pedig nem környezet-független, de környezetfüggő, függetlenül
a számrendszer alapjától és a polinomtól.
Formálisan, ha p egy polinom, és B ł 1 egy szám, akkor jelölje L(p,B) = (p(N)ÇN)B, ahol az alsó index B a B alapú számrendszerben való felírást jelenti, N = {0,1,2,Ľ}.
Tétel.
Legyen p(x) = arxr+Ľ+a1x+a0 egy tetszőleges
egész-együtthatós polinom, melyre r ł 1 és ar > 0,
továbbá legyen B ł 1 egész!
Ekkor L(p,B) nem környezet-független, ha r ł 2, és
reguláris, ha r = 1.
A tétel bizonyításában a cikk elsősorban a Bar-Hillel lemmára, illetve véges automaták elemi tulajdonságaira hivatkozik. A bizonyítás szétválik az r ł 3, r = 2 és r = 1 esetekre, miközben felhasznál két egyszerű lemmát.
A cikk második részében az előző tétel erősebb változata szerepel: Belátjuk, hogy a polinomra tett feltételek gyengítése mellett is teljesül az állítás. Nevezetesen a polinom lehet tetszőleges komplex együtthatós, amennyiben p(n) Î N teljesül véges sok kivételével minden n Î N esetén.
A dolgozat egy sejtéssel zárul, melyben a polinomra tett megszorítás még gyengébb, és az állítás továbbra is az, hogy L(p,B) sohasem lehet nem reguláris környezet-független.
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:
P. Dömösi, S. Horváth, M. Ito, L. Kászonyi, and M. Katsura.
Formal languages consisting of primitive words.
Lecture Notes in Computer Science, 710:194-, 1993.
Rövid cím: Primitív szavak nyelve.
Megjegyzés: A cikket ketten is előadhatják.
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
megmutatja, hogy Q teljesít két erős feltételt,
mindkettő szükséges feltétele a környezet-független nyelveknek.
Az első feltétel Bader és Moura feltételének erősítése (erős BM feltétel). Minden környezet-független nyelv rendelkezik a következő tulajdonsággal:
Definíció.
Legyen L Í T* egy nyelv. Akkor mondjuk, hogy L
teljesíti az erős BM feltételt, ha létezik olyan
n ł 2 egész, hogy minden z Î L szóra,
ha z-ben d pozíció kitüntetett és
e ł 0 pozíció kizárt, ahol d > n1+e,
akkor z faktorizálható a következő módon:
z = uvwxy, ahol
Figyeljük meg, hogy d = |z|, e = 0 választással a jól ismert Bar-Hillel lemmát kapjuk. A cikk szerzői belátják, hogy Q teljesíti az erős BM feltételt.
A cikk további részében a szerzők megmutatják, hogy Q egy speciális részhalmaza nem környezet-független, de megadnak végtelen sok olyan reguláris R nyelvet, melyekre QÇR környezet-független.
Pontos bibliográfiai adatok:
Horváth Sándor.
Primitive words are strongly interchangeable but nonlinear.
Technical Report FBI-HH-B-183/96, Universität Hamburg Fachbereich
Informatik, Vogt-Kölnn-Strasse 30, D-22527 Hamburg, Germany, January 1996.
Rövid cím: Erős kicserélhetőség.
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 négy eredményt közül,
ami közelebb hozhatja a megoldást.
A szerző bevezeti az Ogden, Ross és Winklmann kicserélési tulajdonságának egy erősített változatát, majd megmutatja hogy Q rendelkezik ezzel a tulajdonsággal.
Definíció.
Azt mondjuk, hogy egy L Í T* nyelv
erősen kicserélhető, ha
létezik olyan c > 0 konstans, melyre
minden n ł 2, i ł 0 és j ł 1 esetén,
ahol j < n és i+j Ł n, és minden
H Í LÇTn nem üres halmazra
létezik H˘ Í H a következő tulajdonságokkal:
A dolgozat további részében a szerző bizonyítja, hogy a legfeljebb n hosszú primitív szavak sűrűsége exponenciális gyorsasággal tart 0-hoz n növekedtével, valamint azt, hogy Q nem korlátos nyelv, és nem is lineáris.
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.
Megjegyzés: A cikket ketten is előadhatják.
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.
Megjegyzés: A cikket ketten is előadhatják.
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:
Lila Kari, Gheorghe Paun, Gabriel Thierrin, and Sheng Yu.
At the crossroads of dna computing and formal languages:
Characterizing recursively enumerable languages using insertion-deletion
systems.
In Proceedings of the 3rd DIMACS Workshop on DNA Based
Computers, held at the University of Pennsylvania, June 23 - 25, 1997,
pages 318-333, June 1997.
Rövid cím: Beszúró-törlő rendszerek.
Megjegyzés: A cikket ketten is előadhatják.
A formális nyelvek elméletében a leggyakoribb generáló mechanizmus
az újraírás. A természetes nyelvek vizsgálata során merült fel a
gondolat, hogy az újraírás mellett, vagy helyett szövegrészek
beszúrásával, vagy törlésével képezzünk új szövegeket.
E módszerek a molekuláris számítások
szempontjából is rendkívül fontosak, mert különböző enzimek
segítségével DNS, illetve RNS molekulákon megvalósíthatóak
bizonyos (a környezettől is függő) beszúrások és törlések.
A cikk a beszúró-törlő rendszerek több alosztályáról belátja,
hogy az általuk generált nyelv megegyezik a rekurzívan
felsorolható nyelvekkel.
Definíció.
Beszúró-törlő rendszeren a következő konstrukciót értjük:
ahol V egy abc, T Í V, A Í V*,
I,D Í V*×V*×V* véges halmazok.
g = (V,T,A,I,D),
T a rendszerünk terminális abc-je, A az axiómák, I a beszúró, D a törlő szabályok halmaza. (u,z,v) Î I azt jelenti, hogy ha egy szóban előfordul az uv részszó, akkor u és v közé beszúrhatjuk a z szót. (u,z,v) Î D azt jelenti, hogy ha egy szóban előfordul az uzv részszó, akkor u és v közül kitörölhetjük a z szót.
x,y Î V* esetén xŢy pontosan akkor áll fenn, ha a következők egyike teljesül:
Jelölje Ţ* a Ţ reláció reflexív, tranzitív lezártját. A g
által generált nyelv:
|
Pontos bibliográfiai adatok:
Kenichi Morita.
Universality of a reversible two-counter machine.
Theoretical Computer Science, 168(2):303-320, 20 November
1996.
Rövid cím: Két-számlálójú gép.
Megjegyzés: A cikket ketten is előadhatják.
A k-számlálójú gép (CM(k)) egy olyan automata, aminek
k számláló áll rendelkezésre segédmemóriaként.
Minsky megmutatta, hogy
bármely Turing gépet
lehet szimulálni egy CM(2)-beli géppel.
Ez a cikk a reverzibilis (visszafelé determinisztikus)
számláló gépekkel foglalkozik.
Először megmutatja, hogy bármely CM(k) gép szimulálható egy
reverzibilis CM(k+2) géppel, majd bebizonyítja, hogy
minden reverzibilis CM(k) gép szimulálható egy
reverzibilis CM(2)-belivel.
Definíció.
k-számlálójú gép alatt a következőt értjük:
ahol k a szalagok (vagy számlálók) száma,
Q az állapotok véges, nem üres halmaza,
q0 Î Q a kezdőállapot,
qf Î Q a végső állapot.
A szalagok abc-je {Z,P}, ahol P az üres szimbólum.
d a konfiguráció-átmeneti reláció:
d Í (Q×{1,Ľ,k}×{Z,P}×Q)Č(Q×{1,Ľ,k}×{-,0,+}×Q).
A -, 0, + szimbólumok balra mozgást, helyben maradást,
illetve jobbra mozgást jelentenek.
A szalagok egy irányba (jobbra) végtelen hosszúak,
a legbaloldali pozícióban a Z szimbólum szerepel,
az összes többiben pedig a P.
(Z a zérus, P a pozitív rövidítése.)
M = (k,Q,d,q0,qf),
d minden eleme egy négyes, alakja vagy (q,i,s,q˘), vagy (q,i,d,q˘), ahol q,q˘ Î Q, s Î {Z,P}, d Î {-,0,+}. A (q,i,s,q˘) négyes azt jelenti, hogy ha a gép a q állapotban van, és az i. olvasófej alatt az s szimbólum található, akkor átmehet a q˘ állapotba. A (q,i,d,q˘) négyes azt jelenti, hogy ha a gép a q állapotban van, átmehet a q˘ állapotba, és az i. olvasófej balra, jobbra, vagy nem mozog egy pozíciót d értéke szerint.
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.
Megjegyzés: A cikket ketten is előadhatják.
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.)
A [3], [5], [6], [7], [8], [9] cikkeket ketten is előadhatják.
Szükséges feltételek környezet-független nyelvekre
Egyéb témák
Tartalék cikkek