Hogere-orde logica's en structuren (R-6738)

Het grootste deel van het onderzoek rond de theorie van querytalen wordt geleid door de zoektocht naar het vinden van een goede balans tussen de expressieve kracht van een model en hoe makkelijk het model te controleren/gebruiken is. De algemene trend is om te beginnen met een zwakke logica qua expressiviteit over eindige modellen, en vervolgens conservatief uitbreiden met andere constructen die de expressieve kracht verhogen. Het moeilijkste gedeelte is om dit te doen zonder dat de resulterende verlengde talen te gecompliceerd worden en niet meer efficiënt kunnen gebruikt worden. Op dit vlak is eerste-orde logica uitgebreid met verschillende soorten vaste punten en telwoorden zoals tellen en transitieve afsluiting reeds uitgebreid bestudeerd. Uitbreidingen van de eerste-orde logica naar een hogere orde logica hebben niet dezelfde aandacht gekregen op dit vlak, omdat in de bestaande tweede-orde logica NP al is opgenomen. In dit project stellen we een andere aanpak voor. Onze uitgangspunten zijn hogere orde talen die over het algemeen zeer complex zijn, maar ook zeer expressief en op die manier waardevol als een instrument voor de specificatie van query's op een hoger niveau. Dan in plaats van zich te concentreren op manieren om deze talen eenvoudiger te maken door verschillende syntactische beperkingen (hetgeen een gebruikelijke aanpak zou zijn), concentreren wij ons op hoe deze zeer expressieve talen kunnen worden gebruikt om eenvoudigere query's uit te drukken. Op deze manier hebben we drie veelbelovende werkpunten geïdentificeerd.

Trefwoorden:Hogere-orde logica

Disciplines:Toegepaste wiskunde

Project type:Samenwerkingsproject