Counting with majority quantifiers

Näytä tavanomaiset kuvailutiedot

dc.contributor University of Helsinki, Faculty of Science, Department of Mathematics and Statistics en
dc.contributor Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Matematiikan ja tilastotieteen laitos fi
dc.contributor Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten, Institutionen för matematik och statistik sv
dc.contributor.author Koskinen, Miikka
dc.date.accessioned 2018-12-11T13:42:15Z
dc.date.available 2018-12-11T13:42:15Z
dc.date.issued 2018-09-24
dc.identifier.uri URN:NBN:fi-fe201804208631
dc.identifier.uri http://hdl.handle.net/10138/273540
dc.description.abstract 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. fi
dc.language.iso en
dc.publisher University of Helsinki en
dc.publisher Helsingin yliopisto fi
dc.publisher Helsingfors universitet sv
dc.title Counting with majority quantifiers en
dc.type.ontasot master's thesis en
dc.type.ontasot pro gradu -tutkielmat fi
dc.type.ontasot pro gradu-avhandlingar sv
dc.type.dcmitype Text
dc.subject.discipline Mathematics en
dc.subject.discipline Matematiikka fi
dc.subject.discipline Matematik sv
dct.identifier.urn URN:NBN:fi-fe201804208631

Tiedostot

Tiedosto(t) Koko Formaatti Näytä

Tähän julkaisuun ei ole liitetty tiedostoja

Viite kuuluu kokoelmiin:

Näytä tavanomaiset kuvailutiedot