Browsing by Author "Koskinen, Miikka"

Työssä tarkastellaan majoriteettikvanttorien ilmaisuvoimaa sanamallien kontekstissa. Kuten eksistenssikvanttori (∃) ja universaalikvanttori (∀), majoriteettikvanttori on looginen kvanttori. Sillä voidaan ilmaista väitteen pätevän yli puolelle tarkasteltavan mallin perusjoukon alkioista. Deskriptiivisen vaativuusteorian näkökulmasta uniformi TC⁰-piirivaativuusluokka vastaa ensimmäisen kertaluvun logiikkaa yhteenlaskulla, kertolaskulla ja majoriteettikvanttorilla varustettuna. Työssä tutkitaan TC⁰-luokan sisäistä rakennetta rajoittamalla tarkastelu loogiseen fragmenttiin, jossa käyttettävissä on vain majoriteettikvanttori ja järjestysrelaatio. Työssä osoitetaan, että sekä eksistenssi- että universaalikvanttoria voidaan simuloida majoriteettikvanttorin ja järjestysrelaation avulla. Myös yhteenlasku ja perusjoukon parillisuus ovat ilmaistavissa. Sen sijaan kertolasku ei ole ilmastavissa yksipaikkaisella majoriteettikvanttorilla. Lisäksi työssä osoitetaan, että kertolasku voidaan ilmaista kaksipaikkaisella majoriteettikvanttorilla. Tästä seuraa, että kaksipaikkainen majoriteettikvanttori on aidosti voimakkaampi kuin yksipaikkainen majoriteettikvanttori.