Title: Random Boolean functions induced by random Boolean expressions
Language: English
Authors: Haim, Clemens 
Qualification level: Diploma
Advisor: Gittenberger, Bernhard 
Issue Date: 2016
Number of Pages: 119
Qualification level: Diploma
Abstract: 
We consider a set of Boolean expressions with a probability measure on it and call this our model. This model induces a probability measure on the Boolean functions. The induced probability depends strongly on the underlying Boolean expressions, so we consider several different sets of Boolean expressions, i.e. different models, distinguished by the connectors they are built with and/or by the structure of the expressions. We examine the relation between the underlying class of Boolean expressions and the induced probability and investigate the shape and its properties. We study the question if this probability measure has a limit when the size of the underlying Boolean expressions tends to infinity. The aim of this thesis is to give a broad overview of several different set-ups for such models considered in the literature with a slight focus on models that allow interesting conclusions regarding the number of satisfiable assignments of read-one expressions.
Keywords: random Boolen functions; random Boolean expression; Shannon effect
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-89312
http://hdl.handle.net/20.500.12708/3594
Library ID: AC13006453
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

15
checked on Jun 26, 2021

Download(s)

68
checked on Jun 26, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.