velikost textu

Interval Representations of Boolean Functions

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Interval Representations of Boolean Functions
Název v češtině:
Intervalové reprezentace booleovských funkcí
Typ:
Disertační práce
Autor:
RNDr. David Kronus, Ph.D.
Školitel:
doc. RNDr. Ondřej Čepek, Ph.D.
Oponenti:
prof. RNDr. Jiří Sgall, DrSc.
RNDr. Petr Savický, CSc.
Id práce:
40913
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra teoretické informatiky a matematické logiky (32-KTIML)
Program studia:
Informatika (P1801)
Obor studia:
Teoretická informatika (I1)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
22. 8. 2007
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Abstract v angličtině:
This thesis is dedicated to a research concerning representations of Boolean functions. We present the concept of a representation using intervals of integers. Boolean function f is represented by set I of intervals, if it is true just on those input vectors, which correspond to integers belonging to intervals in I, where the correspondence between vectors and integers depends on the ordering of bits determining their significancies. We define the classes of k-interval functions, which can be represented by at most k intervals with respect to a suitable ordering of variables, and we provide a full description of inclusion relations among the classes of threshold, 2-monotonic and k-interval Boolean functions (for various values of k). The possibility to recognize in polynomial time, whether a given function belongs to a specified class of Boolean functions, is another fundamental and practically important property of any class of functions. Our results concerning interval functions recognition include a proof of co-NP- hardness of the general problem and polynomial-time algorithms for several restricted variants, such as recognition of 1-interval and 2-interval positive functions. We also present an algorithm recognizing general 1-interval functions provided that their DNF representation satisfies several (quite strong) conditions. For 2-monotonic or threshold functions we costruct an algorithm finding an interval representation with the minimum number of intervals. The extension problem for interval functions involves deciding, whether a given partially defined function can be extended to a k-interval function, and we present polynomial-time algorithms solving it for the classes of positive 1-interval, general 1-interval and renamable 1-interval functions. In the best-fit extension problem, which generalizes the extension problem, we are given a partially defined function and our task is to find a totally defined k-interval function, which disagrees with the input Powered by TCPDF (www.tcpdf.org)
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. David Kronus, Ph.D. 604 kB
Stáhnout Abstrakt v českém jazyce RNDr. David Kronus, Ph.D. 150 kB
Stáhnout Abstrakt anglicky RNDr. David Kronus, Ph.D. 152 kB
Stáhnout Posudek vedoucího doc. RNDr. Ondřej Čepek, Ph.D. 218 kB
Stáhnout Posudek oponenta prof. RNDr. Jiří Sgall, DrSc. 202 kB
Stáhnout Posudek oponenta RNDr. Petr Savický, CSc. 47 kB
Stáhnout Záznam o průběhu obhajoby 211 kB