Itsepäinen joukko.

Rinnakkaisissa järjestelmissä on sellainen hauska piirre, että kun niiden käyttäytymistä mallinnetaan esim. tilakoneina, joilla on ns. lomitetun ajan semantiikka (interleaving semantics), periaatteessa toisistaan täysin riippumattomat tapahtumat tuottavat "eri" tulevaisuuden.

Esimerkikki: järjestelmä, jossa kaksi komponenttia, A ja B toimivat toisistaan riippumatta; A vilkuttaa punaista valoa ja B vihreää (tämä on vain esimerkki, ei mikään mielekäs järjestelmä) ja kolmas komponetti odottaa, että kumpikin valo on vilkkunut viisi kertaa ja sitten se piippaa. Olemme kiinnostuneita tulevaisuudesta, jossa tapahtuu "piippaus". A ja B vilkkuvat miten sattuu; niillä on viidenteen valon syttymiseen asti yhteensä 36 eri tilayhdistelmää (6*6). Tämä on vähän hölmöä, koska oikeasti olemme kiinnostuneita kummankin kuudesta tilasta, eikä näiden muilla yhdistelmillä ole merkitystä kuin sillä, jossa molemmat ovat vilkkuneet jo viisi kertaa.

Jokaisessa tilassa ennen kuin jompi kumpi lamppu vilkkunnut viisi kertaa, järjestelmä voi toimia kahdella eri tavalla: joko A vilkkuu tai B vilkuu. A:n vilkkuminen ei estä B:tä vilkkumasta ja toisaalta B:n vilkkuminen ei estä A:ta vilkkumasta. Lisäksi, tulevaisuus, jossa sekä A että B ovat vilkkuneet kerran, on identtinen, riippumatta siitä, kumpi tapahtuu ensin. Tulevaisuus, jossa "piippaus" tapahtuu, ei jää tutkimatta, vaikka tutkittaisiin vain toinen näistä järjestyksistä. Sanomme, että A ja B ovat riippumattomat mainitussa tilassa.

Riippumattomuuden käsite yleistyy laajemminkin. Oletetaan, että olemme kiinnostuneita tulevaisuuksista, joissa "kaikki" on jo tapahtunut, so. järjestelmä on lopettanut toimintansa. Haluamme säilyttää nämä tulevaisuudet, mutta tutkia mahdollisimman vähän tilasiirtymiä kustakin tilasta. Oletamme, että järjestelmässä on "tapahtumia" ja "tiloja" - en erittele tätä sen tarkemmin.

Sanomme, että joukko T tapahtumia on itsepäinen annetussa tilassa (stubborn, ks esim A stubborn attack on state explosion) jos sillä on seuraavat ominaisuudet:
A1: Jos tapahtuma t kuuluu joukkoon T ja se voidaan suorittaa tulevaisuudessa s', joka saavutetaan suorittamalla tietty sekvenssi joukon ulkopuolisia tapahtumia, se voidaan suorittaa heti. Tällöin lopputulos on riippumaton siitä, suoritetaanko t mainitun sekvenssin jälkeen vai sitä ennen.
A2: Joukosta löytyy yksi tapahtuma, joka voidaan suorittaa heti, ja jonka suorittamista ei voi estää suorittamalla joukon ulkopuolisia tapahtumia. Tätä nimitetään avaintapahtumaksi.

Jos jokaisessa tilassa tutkitaan vain ne tulevaisuudet, jotka saavutetaan tutkimalla itsepäinen joukko tapahtumia, ei hukata ainuttakaan sellaista tulevaisuutta, jossa järjestelmä on pysähtynyt. Tämän todistaminen ei ole vaikeaa: Jos järjestelmä on pysähtynyt, avaintapahtuman on joko täytynyt tapahtua tai sitten se on täytynyt estää. Koska joukon ulkopuoliset tapahtumat eivät voi sitä estää, ja sisäpuolisten tapahtumien tuottamat tulevaisuudet tutkitaan, niin todistus on valmis.

Syystä, joka ei ole minulle täysin ilmeinen, esimerkiksi Wikipedia tuntee ainoastaan itsepäistä joukkoa aidosti heikomman menetelmän, ns. "ample set"-karakterisoinnin riippumattomuutta hyödyntävälle reduktiolle. Karakterisointi on vaikeampi, todistus oikeellisuudesta on vaikeampi ja tiedetään, että reduktio on aidosti huonompi.