We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function f is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit (circuits where negations appear only at the leaves) computing f. We prove trade-off results between the depth and the weight/structure of the orientation vectors in any circuit C computing the CLIQUE function on an n vertex graph. We prove that if C is of depth d and each gate computes a Boolean function with orientation of weight at most w (in terms of the inputs to C), then d×ω must be Ω(n). In particular, if the weights are o(n/logk n), then C must be of depth ω(logk n). We prove a barrier for our general technique. However, using specific properties of the CLIQUE function (used in Amano Maruoka (2005)) and the Karchmer-Wigderson framework (KarchmerWigderson (1988)), we go beyond the limitations and obtain lower bounds when the weight restrictions are less stringent. We then study the depth lower bounds when the structure of the orientation vector is restricted. Asymptotic improvements to our results (in the restricted setting) separates NP from NC. As our main tool, we generalize Karchmer-Wigderson games (Karchmer Wigderson (1988)) for monotone functions to work for non-monotone circuits parametrized by the weight/structure of the orientation. We also prove structural results about orientation and prove connections between number of negations and weight of orientations required to compute a function.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The objective of this article is to define an approach towards generating implications with (or without) negation when only a formal context K = (G,M, I) is provided. To that end, we define a two-step procedure which first (i) computes implications whose premise is a key in the context K| K representing the apposition of the context K and its complementary �K with attributes in M (negative attributes), and then (ii) uses an inference axiom we have defined to produce the whole set of implications.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Górny Śląsk odegrał i odgrywa istotną rolę w rozwoju architektury MoMo w Europie Środkowej, na każdym etapie: od protomodernizmu i wczesnego modernizmu (jugend stil, secesja, nowa estetyka fabryczna, ekspresjonizm) przez dojrzały modernizm (Neues Bauen, funkcjonalizm), jego późną fazę (socmodernizm) aż po najnowszy nurt tzw. nowego modernizmu. W obszarach ochrony obiektów modernistycznych można zaobserwować tu 4 podstawowe modele relacji i odniesień, jak np.: 1. arogancja – negacja, likwidacja, zniszczenie, eksterminacja, wymazywanie z pamięci; 2. bierna tolerancja – obojętność, akceptacja egzystencji z pominięciem zabiegów ochronnych, ignorancja, skazywanie obiektu na powolną śmierć techniczną; 3. akceptacja – dostrzeganie wartości obiektu w środowisku arch.-urb., ochrona prawna, modernizacja, konserwacja, utrzymywanie właściwego stanu technicznego; 4. kontynuacja – dostrzeganie wybitnych wartości obiektu w środowisku arch.-urb., ochrona prawna, modernizacja, konserwacja, twórcze kultywowanie wartości kulturowych w nowych obiektach. Geneza negatywnych zachowań związana jest z wszechobecnym syndromem zrywania ciągłości historycznej. To nie tylko choroba o zasięgu regionalnym, ale wręcz narodowa epidemia.
EN
Upper Silesia has been played quite important role in developing MoMo architecture in Central Europe at every stage: from protomodernism and early modernism (jugend stil, art nouveau, a new factory aesthetic, expressionism) by mature stage of modernism (Neues bauen, functionalism –international style), the late stage of modernism – socialist modernism, called “socmodernism” to the latest trend – new modernism. In the areas of conservation of modernist buildings you can see 4 basic models of relationships and references, such as: 1. arrogance – negation, elimination, destruction, extermination, erasing the memory; 2. passive tolerance – indifference, acceptance of life without the protective treatments, ignorance, convict object to a slow technical death; 3. acceptance – perception of values of object in environment, law protection, modernization, maintenance of proper technical state; 4. continuance – perception of excellent object values in environment, law protection, modernization, maintenance, cultivating a creative cultural values to new objects. Origin of negative behavior is linked to the ubiquitous syndrome severing of historical continuity. It is not just a disease of the regional, but even the national epidemic.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Discrete dualities are presented for Heyting algebras with various modal operators, for Heyting algebras with an external negation, for symmetric Heyting algebras, and for Heyting-Brouwer algebras.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.