Polinomok értékkészlete minden számrendszerben nem környezet–független, vagy reguláris

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) = a_{r}x^{r} + … + a_{1}x + a_{0} egy tetszőleges egész–együtthatós polinom, melyre r ≥ 1 és a_{r} > 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.

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^{n} halmazra és minden olyan m egészre, melyre n ≥ m ≥ 2 létezik k ≥ |Q|/(cn^{2}) egész és z_{1}, …, z_{k} ∈ Q szavak a következő tulajdonságokkal:

1. z_{i} = w_{i}x_{i}y_{i}, i = 1, …, k,

2. |w_{1}| = |w_{2}| = ⋯ = |w_{k}|,

3. |y_{1}| = |y_{2}| = ⋯ = |y_{k}|,

4. m ≥ |x_{1}| = |x_{2}| = ⋯ = |x_{k}| > m/2, és

5. w_{i}x_{j}y_{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.

Primitív szavak nyelve

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^{+}\{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 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 > n^{1+e}, akkor z faktorizálható a következő módon: z = uvwxy, ahol

1. w tartalmaz kitüntetett pozíciót,

2. vagy u és v, vagy x és y mindegyike tartalmaz kitüntetett pozíciót,

3. vx nem tartalmaz kizárt pozíciót,

4. ha a kitüntetett és kizárt pozíciók száma vwx-ben rendre r és s, akkor r ≤ n^{1+s}, végül

5. minden m ≥ 0 számra uv^{m}wx^{m}y ∈ L.

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.

A primitív szavak nyelve erősen kicserélhető, de nem lineáris

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^{+}\{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 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 ∩ T^{n} nem üres halmazra létezik H′ ⊆ H a következő tulajdonságokkal:

1. |H′| > |H|/c

2. x, y ∈ H′ esetén, ha x = x_{1}x_{2}x_{3}, y = y_{1}y_{2}y_{3}, ahol |x_{1}| = |y_{1}| = i, |x_{2}| = |y_{2}| = j, teljesül a következő: x_{1}y_{2}x_{3}, y_{1}x_{2}y_{3} ∈ L.

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.

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. 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^{+}\{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)^{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:

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^{m}wx^{m}y ∈ 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_{1}, u_{2}, u_{3} ∈ T^{∗} esetén, ha {u_{1}xu_{2}xu_{3} | x ∈ Y^{+}} ⊆ L, akkor létezik olyan x′, x′′ ∈ Y^{+}, x′ ≠ x′′, melyre u_{1}x′u_{2}x′′u_{3} ∈ 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. 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 ∩ T^{n} 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^{n}.

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 ybó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 <^{m} y (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_{1}, u_{2}, u_{3} ∈ T^{∗} szóra és minden R ⊆ T^{∗} × T^{∗} nem korlátos relációra, ha {u_{1}xu_{2}yu_{3} | R(x, y)} ⊆ L, akkor létezik olyan m egész, hogy minden x, y ∈ T^{∗} esetén

|x|, |y| > m ∧ R(x, y) ⟹ ∃x′, y′ : (x′, y′) <_{m} (x, y) ∧ u_{1}x′u_{2}y′u_{3} ∈ L.

A rekurzívan felsorolható nyelvek jellemzése beszúró–törlő rendszerek segítségével

Pontos bibliográfiai adatok: Lila Kari, Gheorghe Păun, 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:

γ = (V, T, A, I, D),

ahol V egy abc, T ⊆ V, A ⊆ V^{∗}, I, D ⊆ V^{∗} × V^{∗} × V^{∗} véges halmazok. 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:

• x = x_{1}uvx_{2}, y = x_{1}uzvx_{2}, x_{1}, x_{2} ∈ V^{∗} és (u, z, v) ∈ I

• x = x_{1}uzvx_{2}, y = x_{1}uvx_{2}, x_{1}, x_{2} ∈ V^{∗} és (u, z, v) ∈ D

Jelölje ⟹^{∗} a ⟹ reláció reflexív, tranzitív lezártját. A γ által generált nyelv:

L(γ) = {w ∈ T^{∗} | x ⟹^{∗} w, x ∈ A}.

A reverzibilis két–számlálójú gép univerzalitásáról

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:

M = (k, Q, δ, q_{0}, q_{f}),

ahol k a szalagok (vagy számlálók) száma, Q az állapotok véges, nem üres halmaza, q_{0} ∈ Q a kezdőállapot, q_{f} ∈ Q a végső állapot. A szalagok abc-je {Z, P }, ahol P az üres szimbólum. δ a konfiguráció–átmeneti reláció: δ ⊆ (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.)

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

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. 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: () → ϵ, és [] → ϵ.)

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

Formális nyelvek szeminárium, 2000 Tervezett program

A [3], [5], [6], [7], [8], [9] cikkeket ketten is előadhatják.

Szükséges feltételek környezet–független nyelvekre

[1] Horváth Sándor. Ranges of polinomials are not context-free in any number system. To appear in PuMa, June 1998.

[2] 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.

[3] 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.

[4] 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.

[5] 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.

[6] R. Boonyavatana and G. Slutzki. The interchange or pump (DI)lemmas for context-free languages. Theoretical Computer Science, 56(3):321–338, March 1988.

Egyéb témák

[7] Lila Kari, Gheorghe Păun, 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.

[8] 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.

[9] Kenichi Morita. Universality of a reversible two-counter machine. Theoretical Computer Science, 168(2):303–320, 20 November 1996.

Tartalék cikkek

[10] Arto Salomaa. Abstact Families of Languages, In: Formal Languages, chapter IV, pages 123–141. Academic Press, New York, 1973.

[11] Arto Salomaa. Finite non–deterministic and probabilistic automata, In: Theory of Automata, chapter II, pages 71–93. Pergamon Press, 1969.