torstai 15. lokakuuta 2009

Matkalla III.

Istuin aamupäivän sumussa. Aikaeroväsymys helpottaa pikku hiljaa, mutta aamupäivä oli silti vaikea. Lounaan jälkeen mieleni avautui salaman lailla. Eräs esitelmä käsitteli Büchi-automaatin, tai oikeastaan sen yleistetyn muodon, epätyhjyyden tarkastavan algoritmin sovellusta Streett-automaatin tyhjyyden tarkastukseen. Luulen, että keksin välittömästi parannuksen algoritmiin.

Streett-automaatti ja erityisesti sellainen muotoa, jossa hyväksymisehdot on koodattu transitioiksi, voidaan todeta epätyhjäksi löytämällä sieltä ääretön polku, jolla streett-hyväksymisehdot toteutuvat. Ehdot koodataan transitioiksi muotoa "jos p_i tapahtuu äärettömän monta kertaa, niin q_i tapahtuu äärettömän monta kertaa". Tässä i voi olla suurikin; jokaisen ehdon täytyy toteutua. Ehto toteutuu tietysti triviaalisti jos kumpikaan ei tapahdu.

Reiluus (erilaiset ehdot sille, että jos tapahtuma on riittävän usein mahdollinen, niin sen pitää myös joskus tapahtua) on helppo koodata Streett-automaatilla. Tavallisesti yleistetty Büchi-automaatti vaatii pahimmillaan eksponentiaalisen määrän tiloja suhteessa reiluusehtojen määrään. Streett-automaatti pärjää ehtojen muodosta riippuen vakio- tai lineaarisella määrällä.

Tarkastaminen on vaikeahkoa. Esitetty algoritmi joutuu tutkimaan ensin kokonaisen vahvan komponentin, lisäämään siihen rajoitusehtoja, ja tutkimaan sen uudelleen, pahimmassa tapauksessa yhtä monta kertaa kuin on ehtoja. Koska komponentissa voi olla paljon tiloja, tämä moninkertaistuminen ei ole toivottavaa. Uskoisin, että lisäehdot saadaan aikaan lisätyöllä, joka ei vaadi tilojen tutkimista useampaan kertaan, ainoastaan transitioiden tutkimisen lykkäämistä.

Kävimme eilen illallisella ja kävelimme keskustan varsinaisen kasinoalueen läpi. Kontrasti vähän sivummalla sijaitseviin alueisiin on suuri, vaikka ei täälläkään nyt mitään kauheaa slummia ole. Tänään on konferenssi-illallinen. Vaimo lähti käymään Venetianissa. Paikassa on kanaalijärjestelmä sisätiloissa. Tämä on postmodernin konsumerismin ja kapitalismin jonkinlainen huipentuma.

Konferenssin esitelmät ovat varsinaisen yliopiston sijaan Macau Polytechnic Instituten tiloissa. Ovella mitataan ruumiinlämpö kameralla ja joka paikassa kehotetaan desinfioimaan kädet. Kaikki kosketettavat pinnat, kuten kahvat, hissien napit jne. desinfioidaan parin tunnin välein. Täällä ilmeisesti otetaan jotenkin ihmeen vakavissaan influenssan uhka. En sinänsä protestoi, mutta pistää miettimään, kuinka suuri rajahyöty siitä mahtaa olla.

Huomenna lähden Hong Kongiin pariksi päiväksi. Palaan tänne sunnuntaina tekemään töitä.

2 kommenttia:

rebyk kirjoitti...

Täällä ilmeisesti otetaan jotenkin ihmeen vakavissaan influenssan uhka. En sinänsä protestoi, mutta pistää miettimään, kuinka suuri rajahyöty siitä mahtaa olla.

Ehkä siellä halutaan esittää, että juuri sinun ja muiden vieraiden vuoksi nähdään vaivaa ja tehdään kaikki mahdolliset varotoimenpiteet.

Anonyymi kirjoitti...

Kansainvälistä akateemista elämää parhaimmilaan. Uusia ideoita, uusia vaikutteita. Vieraita kulttuureita ja uusia tuttavuuksia.