search query: @keyword normalization / total: 5
reference: 1 / 5
« previous | next »
Author:Bomanson, Jori
Title:Developing Efficient Encodings for Weighted Expressions in Answer Set Programs
Tehokkaiden esitystapojen kehittäminen painosäännöille vastausjoukko-ohjelmissa
Publication type:Master's thesis
Publication year:2014
Pages:85      Language:   eng
Department/School:Perustieteiden korkeakoulu
Main subject:Tietojenkäsittelytiede   (IL3010)
Supervisor:Janhunen, Tomi
Instructor:Gebser, Martin
Electronic version URL: http://urn.fi/URN:NBN:fi:aalto-201408292568
OEVS:
Electronic archive copy is available via Aalto Thesis Database.
Instructions

Reading digital theses in the closed network of the Aalto University Harald Herlin Learning Centre

In the closed network of Learning Centre you can read digital and digitized theses not available in the open network.

The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/

You can read theses on the Learning Centre customer computers, which are available on all floors.

Logging on to the customer computers

  • Aalto University staff members log on to the customer computer using the Aalto username and password.
  • Other customers log on using a shared username and password.

Opening a thesis

  • On the desktop of the customer computers, you will find an icon titled:

    Aalto Thesis Database

  • Click on the icon to search for and open the thesis you are looking for from Aaltodoc database. You can find the thesis file by clicking the link on the OEV or OEVS field.

Reading the thesis

  • You can either print the thesis or read it on the customer computer screen.
  • You cannot save the thesis file on a flash drive or email it.
  • You cannot copy text or images from the file.
  • You cannot edit the file.

Printing the thesis

  • You can print the thesis for your personal study or research use.
  • Aalto University students and staff members may print black-and-white prints on the PrintingPoint devices when using the computer with personal Aalto username and password. Color printing is possible using the printer u90203-psc3, which is located near the customer service. Color printing is subject to a charge to Aalto University students and staff members.
  • Other customers can use the printer u90203-psc3. All printing is subject to a charge to non-University members.
Location:P1 Ark Aalto  1755   | Archive
Keywords:answer set programming
cardinality rule
normalization
translation
weight rule
weighted expression
kardinaliteettisääntö
käännös
normalisointi
painosääntö
vastausjoukko-ohjelmointi
Abstract (eng):Answer set programming is a declarative problem solving paradigm suitable for searching solutions to combinatorial search problems.
Propositional answer set programs, studied in this thesis, consist of rules that state logical connections between atomic propositions, or atoms.
A program represents the problem of finding truth assignments, called answer sets, that satisfy the rules in the program, under the condition that by default atoms are false.
Answer set programming can be used as a general purpose problem solving mechanism, by writing programs whose answer sets correspond to solutions of a chosen search problem, and then using automated tools to find them.

In this work, we focus on normalizing a particular type of rules, weight rules, into so called normal rules.
We develop normalization strategies that extend existing translations applied in answer set programming and propositional satisfiability checking.
In particular, we propose to incorporate a base selection heuristic and a structure sharing algorithm into a weight rule translation that decomposes the rule in a mixed-radix base.
Both the previous and novel techniques have been implemented in a normalization tool, and we experimentally evaluate the effect of our methods on search performance.
The proposed techniques improve on the compared normalization methods in terms of conciseness, the number of conflicts encountered during search, and the amount of time needed to find answer sets using a state-of-the-art solving back-end.
On certain benchmark classes, the normalization techniques improve even on native weight-handling capabilities of the solver.
Abstract (fin):Vastausjoukko-ohjelmointi on kombinatoristen hakuongelmien ratkontaan soveltuva ongelmanratkontamenetelmä, jossa ohjelmointi koostuu loogisten yhteyksien deklaratiivisestä määrittelemisestä.
Työssä käsitellyt vastausjoukko-ohjelmat koostuvat säännöistä, jotka määräävät atomisten lauseiden, tai atomien, väliset yhteydet.
Tämänmuotoiseen ohjelmaan kytkeytyy formaali ongelma, jonka ratkaisemiseksi on löydettävä yksi tai useampi totuusjakelu näille atomeille, eli vastausjoukko, joka täyttää ohjelmaan kirjatut säännöt.
Jokainen atomi on lisäksi asetettava epätodeksi paremman tiedon puutteessa.
Vastausjoukko-ohjelmointi muodostaa yleiskäyttöisen ongelmanratkontamekanismin, sillä on mahdollista kirjoittaa ohjelma jonka vastausjoukoista on luettavissa kiinnostuksen kohteena olevan hakuongelman ratkaisut ja näiden vastausjoukkojen etsintää varten löytyy automatisoituja työkaluja.

Tässä diplomityössä keskitytään erilaisten sääntötyyppien välisiin muunnoksiin ja erityisesti niin kutsutuiden painosääntöjen uudelleenkirjoittamiseen vain normaalisääntöjä käyttäen.
Työn tavoitteena on kehittää tähän soveltuvia normalisointimenetelmiä olemassaolevien tekniikoiden pohjalta.
Diplomityössä esitellään uusi heuristiikka sekakannan hakemiseksi sekä rakenteenjakoalgoritmi erään normalisointimenetelmän vaatiman atomi- ja sääntömäärän karsimiseksi.
Näiden ja muiden tekniikoiden käyttöä varten on kirjoitettu tietokoneohjelma, jonka avulla tehtyjä kokeellisia tuloksia esitellään lopuksi.
Saatujen tuloksien perusteella työssä kehitetyt tekniikat tuovat parannuksia muunnoksien tiiviyteen, haussa kohdattujen umpikujien määriin sekä erään johtavan ratkaisinohjelman aikavaatimuksiin.
Tiettyjen testiongelmien kohdalla työssä esitetyt tekniikat auttavat ylittämää jopa ratkaisinohjelmaan sisäänrakennettujen painosääntömenetelmien tehokkuuden.
ED:2014-08-31
INSSI record number: 49695
+ add basket
« previous | next »
INSSI