Counting with majority quantifiers

Show simple item record

dc.contributor Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Matematiikan ja tilastotieteen laitos fi
dc.contributor University of Helsinki, Faculty of Science, Department of Mathematics and Statistics en
dc.contributor Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten, Institutionen för matematik och statistik sv
dc.contributor.author Koskinen, Miikka
dc.date.issued 2018
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 Helsingin yliopisto fi
dc.publisher University of Helsinki en
dc.publisher Helsingfors universitet sv
dc.title Counting with majority quantifiers en
dc.type.ontasot pro gradu -tutkielmat fi
dc.type.ontasot master's thesis en
dc.type.ontasot pro gradu-avhandlingar sv
dc.subject.discipline Mathematics en
dc.subject.discipline Matematiikka fi
dc.subject.discipline Matematik sv
dct.identifier.urn URN:NBN:fi-fe201804208631

Files in this item

Total number of downloads: Loading...

Files Size Format View
Miikka_Koskinen ... h_Majority_Quantifiers.pdf 974.3Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record