Počet záznamů: 1

A Logical Characteristic of Read-Once Branching Programs

SYSNO ASEP	0506562
Druh ASEP	V - Výzkumná zpráva
Zařazení RIV	Záznam nebyl označen do RIV
Název	A Logical Characteristic of Read-Once Branching Programs
Tvůrce(i)	Žák, Stanislav (UIVT-O)_{SAI, RID}
Vyd. údaje	Prague: ICS CAS, 2019
Edice	Technical Report
Č. sv. edice	V-1270
Poč.str.	16 s.
Jazyk dok.	eng - angličtina
Země vyd.	CZ - Česká republika
Klíč. slova	branching programs ; computational complexity ; logic
Vědní obor RIV	IN - Informatika
Obor OECD	Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Institucionální podpora	UIVT-O - RVO:67985807
Anotace	We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two appropriate properties: i) The ”knowledge” arising at a stage of computation in question is derivable from the ”knowledge” arising at the previous stage according to the rules of the model and according to the local arrangement of the b.p. ii) The model confirms the intuitively well-known fact that the knowledge arising at a node of a computation depends not only on it but in some cases also on a ”mystery” information. (I. e. different computations reaching the same node may have different knowledge(s) arisen at it.) We prove that with respect to our model no such information exists in read-once b.p.‘s but on the other hand in b. p.‘s which are not read-once such information must be present. The read-once property forms a frontier. More concretely, we may see the instances of our models as a systems S = (U,D) where U is a universe of knowledge and D are derivation rules. We say that a b.p. P is compatible with a system S iff along each computation in P S derives F (false) or T (true) at the end correctly according to the label of the reached sink. This key notion modifies the classic paradigm which takes the computational complexity with respect to different classes of restricted b.p.‘s (e.g. read-once b.p.‘s, k-b.p.‘s, b.p.‘s computing in limited time etc.). Now, the restriction is defined by a subset of systems and only these programs are taken into account which are compatible with at least one of the chosen systems. Further we understand the sets U of knowledge(s) as a sets of admissible logical formulae. It is clear that more rich sets U‘s imply the large restrictions on b.p.‘s and consequently the smaller complexities of Boolean functions are detected. More rich logical equipment implies stronger computational effectiveness. Another question arises: given a set of Boolean functions (e.g. codes of some graphs) what logical equipment is optimal from the point of complexity?
Pracoviště	Ústav informatiky
Kontakt	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Rok sběru	2020

Počet záznamů: 1