Eilen sain kyykättyä 5x135kg, mikä on uusi ennätys viidellä toistolla, aiemman oltua 132.5kg. En ollut yrittänyt tätä painoa viidellä toistolla, joskin olin kyykännyt 3x140kg, ja uskoisin että olisin kyllä pystynyt tuolloin samaan. Ensi viikon kyykkytreenissä on 140kg vuorossa ja realistinen tavoite on kolme toistoa.
Olen kirjoittanut nyt pari kuukautta artikkelia erääseen Festschrift-kokoelmaan. Aloitin kirjoittamisen kun uskoin että minulla on uusi teoreema. Todistus aina joutui pieniin ongelmiin ja jouduin hieman muokkaamaan teoreeman muotoilua. Sain sen viime viikolla valmiiksi ja nyt oikoluen ja korjailen paperia.
Oletetaan että meillä on suunnattu graafi G jonka kaaret on merkitty aakkoston A symbolein; mukana on myös tyhjä merkki. Lisäksi graafista on osoitettu alkusolmu. Sanotaan että graafin jäljet ovat ne A:n merkkijonot jotka saadaan muodostettua kulkemalla alkusolmusta mikä tahansa polku. Samassa solmussa ja samaa kaarta saa kulkea mielivaltaisen määrän, joten äärelliselläkin graafilla jälkien joukko on usein ääretön. Kaaret ovat joko näkyviä tai näkymättömiä, riippuuen siitä onko kaaren merkki joku A:n symboli vai tyhjä.
Meillä on funktio T, joka jokaisessa graafin solmussa osoittaa tietyt kaaret jotka pitää tutkia, jotta jokin ominaisuus säilyy. Graafin T-reduktio on se graafi, joka saadaan kun otetaan huomioon vain se osa graafista, johon päästään kulkemalla T:n osoittamia kaaria pitkin. Meillä on annettu joukko L joka sisältää sallitut jäljet. Jäljet jotka eivät ole joukossa L, ovat kiellettyjä. Nyt vaaditaan että G:n T-reduktiolla pitää olla kielletty jälki jos G:llä on kielletty jälki. Hyvä, tämä tehdään tietyllä menetelmällä.
Toinen menetelmä on graafihomomorfismi. Kuvataan graafi G graafiksi f(G) homomorfismilla. Homomorfismilla tarkoitetaan kuvausta joka kuvaa solmun s solmuksi f(s) siten, että jos meillä on kaari (s,a,s') -- tässä s on kaaren alkupää, s' on kaaren loppupää ja a on sen merkintä -- niin (f(s),a,f(s')) on f(G):n kaari. Homomorfismi tuottaa graafin jolla on kaikki G:n jäljet mutta voi olla enemmän jälkiä. Näinollen, jos f(G):llä ei ole kiellettyä jälkeä, niin G:lläkään ei voi olla.
Funktion T täytyy toteuttaa joukko erilaisia ominaisuuksia, mutta yleensä funktion arvon laskenta palautuu ns riiipumattoman kaaren käsitteeseen: Jos (s,a,s1) ja (s,b,s2) ovat kaaria jotka lähtevät s:stä, niin ensiksin, pitää löytyä jokin kaari (s1,b,s3) ja (s2,a,s3), sekä aina kun toinen näistä kaarista löytyy, niin pitää löytyä toinen joka vie samaan solmuun. Käytännössä siis tämä tarkoittaa että ei ole väliä kumpi kaarista valitaan solmussa s, aina päästään jatkamaan samaa polkua.
Haluaisimme, että tämä menetelmä yhdistetään homomorfismiin. Homomorfian "läpi" analysoiminen on kuitenkin usein vaikeaa. On hypoteesi, että mutatis mutandis homma toimii jos (s,a,s1) ja (s,b,s2)- kaarten kanssa vaaditaankin että löytyy (s1,b,s3) ja (s2,a,s4) siten että f(s3) = f(s4), eli, riittää että homomorfia takaa "näennäisen riippumattomuuden".
Tällainen tulos oli olemassa tietynlaiselle homomorfialle. Olin siinä uskossa että tämä on totta hyvin yleisessä tapauksessa. Näin ei kuitenkaan ole.
Sanotaan että homomorfia on 1-simulaatio jos aina kun meillä on kaaret (s,a,s') ja (s1,a,s1'), ja f(s) = f(s1) pätee, niin myös f(s') = f(s1') pätee. Tämä on äärimmäisen vahva vaatimus.Mutta sekään ei vielä riitä, sillä sen lisäksi että homomorfian pitää olla 1-simulaatio, sen pitää vielä kaiken lisäksi olla 0-simulaatio, eli jos on kaari (s,a,s') ja f(s) = f(s1), niin pitää olla jokin s2 siten että löytyy kaari (s1, a, s2).
Jos f on siis sekä 0- että 1-simulaatio, niin silloin hypoteesi pätee. Vastaesimerkkejä löytyy kaikille tutkimilleni mielekkäille heikommille ominaisuuksille.
En kuitenkaan löytänyt tiukkaa ehtoa sille, että hypoteesi *ei* pätisi jos f ei ole 0-1-simulaatio (eli bisimulaatio).
Ei kommentteja:
Lähetä kommentti