guest ::
| Home > Academic theses (ETDs) > Doctoral theses > Intervalové reprezentace booleovských funkcí |
Original title:
Intervalové reprezentace booleovských funkcí
Translated title: Interval Representations of Boolean Functions
Authors: Kronus, David ; Čepek, Ondřej (advisor) ; Sgall, Jiří (referee) ; Savický, Petr (referee)
Document type: Doctoral theses
Year: 2007
Language: eng
Abstract: 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...
Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/12250
Permalink: http://www.nusl.cz/ntk/nusl-288067
The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses
Translated title: Interval Representations of Boolean Functions
Authors: Kronus, David ; Čepek, Ondřej (advisor) ; Sgall, Jiří (referee) ; Savický, Petr (referee)
Document type: Doctoral theses
Year: 2007
Language: eng
Abstract: 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...
Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/12250
Permalink: http://www.nusl.cz/ntk/nusl-288067
The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses
Record created 2017-04-25, last modified 2022-03-04