|
|
Lower Bounds on Boolean Formula Size
Fojtík, Vít ; Hrubeš, Pavel (vedoucí práce) ; Savický, Petr (oponent)
Cı́lem této práce je studovat metody konstrukce dolnı́ch odhadů velikosti Booleovských formulı́. Soustředı́me se zde předevšı́m na formálnı́ mı́ry složitosti, přičemž zobecnı́me známou Krapchenkovu mı́ru na třı́du grafových měr, které následně studujeme. Zabýváme se také dalšı́m z hlavnı́ch přı́stupů, využı́vajı́cı́ náhodné restrikce Booleovských funkcı́. Na závěr zmı́nı́me program pro nalezenı́ super-polynomiálnı́ch odhadů založený na KRW doměnce. 1
|
|
|
Classes of Boolean Formulae with Effectively Solvable SAT
Vlček, Václav ; Čepek, Ondřej (vedoucí práce) ; Kullmann, Oliver (oponent) ; Savický, Petr (oponent)
Práce studuje třídy booleovkských formulí pro které je problém splnitelnosti řešitelný v polynomiálním čase. Zaměřuje se na třídy založené jednotkové rezoluci; popisuje třídy unit refutation complete formulí, unit propagation complete formulí a specialně se zaměřuje na třídu SLUR. Shrnuje její vlastnosti a poslední výsledky dosažené v této oblasti. Hlavním výsledkem je coNP-úplnost testování zda daná formule patří do třídy SLUR. V závěru je třída SLUR rozvinuta do několika různých hierarchií a jsou studovány jejich vlastnosti a vzájemný vztah vzhledem k inkluzi. Powered by TCPDF (www.tcpdf.org)
|
|
|
Interval Representations of Boolean Functions
Kronus, David ; Čepek, Ondřej (vedoucí práce) ; Sgall, Jiří (oponent) ; Savický, Petr (oponent)
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...
|
|
|
Cut Languages in Rational Bases
Šíma, Jiří ; Savický, Petr
We introduce a so-called cut language which contains the representations of numbers in a rational base that are less than a given threshold. The cut languages can be used to refine the analysis of neural net models between integer and rational weights. We prove a necessary and sufficient condition when a cut language is regular, which is based on the concept of a quasi-periodic power series. We show that any cut language with a rational threshold is context-sensitive while examples of non-context-free cut languages are presented.
Plný tet: v1236-16 -  PDF
Plný text: content.csg - PDF
|
|
| |
|
| |
|
| |
|
| |
|
| |
|
|
Methods for Multidimensional Event Classification: A Case Study
Bock, R.K. ; Chilingarian, A. ; Gaug, M. ; Hakl, František ; Hengstebeck, T. ; Jiřina, Marcel ; Klaschka, Jan ; Kotrč, Emil ; Savický, Petr ; Towers, S. ; Vaicilius, A. ; Wittek, W.
Plný tet: v887-03 - PDF
Plný text: content.csg - PDF
|
host ::
RSS.