561 research outputs found
Transformations of Boolean Functions
No full textBoolean functions are characterized by the unique structure of their solution space. Some properties of the solution space, such as the possible existence of a solution, are well sought after but difficult to obtain. To better reason about such properties, we define transformations as functions that change one Boolean function to another while maintaining some properties of the solution space. We explore transformations of Boolean functions, compactly described as Boolean formulas, where the property is to maintain is the number of solutions in the solution spaces. We first discuss general characteristics of such transformations. Next, we reason about the computational complexity of transforming one Boolean formula to another. Finally, we demonstrate the versatility of transformations by extensively discussing transformations of Boolean formulas to "blocks," which are solution spaces in which the set of solutions makes a prefix of the solution space under a lexicographic order of the variables
Sequential Relational Decomposition
No full textThe concept of decomposition in computer science and engineering is
considered a fundamental component of computational thinking and is prevalent
in design of algorithms, software construction, hardware design, and more. We
propose a simple and natural formalization of sequential decomposition, in
which a task is decomposed into two sequential sub-tasks, with the first
sub-task to be executed before the second sub-task is executed. These tasks are
specified by means of input/output relations. We define and study decomposition
problems, which is to decide whether a given specification can be sequentially
decomposed. Our main result is that decomposition itself is a difficult
computational problem. More specifically, we study decomposition problems in
three settings: where the input task is specified explicitly, by means of
Boolean circuits, and by means of automatic relations. We show that in the
first setting decomposition is NP-complete, in the second setting it is
NEXPTIME-complete, and in the third setting there is evidence to suggest that
it is undecidable. Our results indicate that the intuitive idea of
decomposition as a system-design approach requires further investigation. In
particular, we show that adding a human to the loop by asking for a
decomposition hint lowers the complexity of decomposition problems
considerably
AllSAT for Combinational Circuits
No full textMotivated by the need to improve the scalability of Intel’s in-house Static Timing Analysis (STA) tool, we consider the problem of enumerating all the solutions of a single-output combinational Boolean circuit, called AllSAT-CT. While AllSAT-CT is immediately reducible to enumerating the solutions of a Boolean formula in Conjunctive Normal Form (AllSAT-CNF), our experiments had shown that such a reduction, followed by applying state-of-the-art AllSAT-CNF tools, does not scale well on neither our industrial AllSAT-CT instances nor generic circuits, both when the user requires the solutions to be disjoint or when they can be non-disjoint. We focused on understanding the reasons for this phenomenon for the well-known iterative blocking family of AllSAT-CNF algorithms. We realized that existing blocking AllSAT-CNF algorithms fail to generalize efficiently for AllSAT-CT, since they are restricted to Boolean logic. Consequently, we introduce three dedicated AllSAT-CT algorithms that are ternary-logic-aware: a ternary simulation-based algorithm TALE, a dual-rail&MaxSAT-based algorithm MARS, and their combination. Specifically, we introduce in MARS two novel blocking clause generation approaches for the disjoint and non-disjoint cases. We implemented our algorithms in our new tool HALL. We show that HALL scales substantially better than any reduction to existing AllSAT-CNF tools on our industrial STA instances as well as on publicly available families of combinational circuits for both the disjoint and the non-disjoint cases
Entailing Generalization Boosts Enumeration
No full textGiven a combinational circuit Γ with a single output o, AllSAT-CT is the problem of enumerating all solutions of Γ. Recently, we introduced several state-of-the-art AllSAT-CT algorithms based on satisfying generalization, which generalizes a given total Boolean solution to a smaller ternary solution that still satisfies the circuit. We implemented them in our open-source tool HALL. In this work we draw upon recent theoretical works suggesting that utilizing generalization algorithms, which can produce solutions that entail the circuit without satisfying it, may enhance enumeration. After considering the theory and adapting it to our needs, we enrich HALL’s AllSAT-CT algorithms by incorporating several newly implemented generalization schemes and additional SAT solvers. By conducting extensive experiments we show that entailing generalization substantially boosts HALL’s performance and quality (where quality corresponds to the number of reported generalized solutions per instance), with the best results achieved by combining satisfying and entailing generalization
Book Review: The Middle Ages : [Rezension zu:] The Middle Ages. Johannes Fried. Harvard University Press. 2015
No full textIn Johannes Fried’s The Middle Ages, the author makes his case for an alternative interpretation of the medieval period as much more sophisticated than commonly thought, writes Ignas Kalpokas. The book intricately traces how ideas and systems of thought that we now consider quintessentially modern European ways of life, thinking and culture stemmed from this time period
Modifying the rat grimace scale for the sub-second assessment of acute pain
No full textThe goal of this study is to improve the way pain is measured in rodents. A previous 2019 publication by Dr. Nathan T. Fried utilized slow-motion videography and statistical modeling to analyze hind paw withdrawal caused by painful stimuli. Upon reanalyzing the one-second slow-motion videos from his study, there was more data in the facial features of the rat, which was not characterized in his work. A 2011 study performed in Dr. Jeffrey Mogil’s lab led to the development of the Rat and Mouse Grimace Scales (RGS, MGS), which measure facial features of pain in these rodents. However, their measurement using the Grimace Scale relied on 30 minutes of video analysis. This project further applies the RGS to the one-second slow-motion videos to assess facial rat grimace in response to different painful stimuli.Winner: Second Place, 2022 Paul Robeson Library Undergraduate Research Award
Revisiting the Fried Chicken Recipe
No full textTwenty-five years ago, Gary Lawson introduced us to legal theory’s tastiest analogy. He told us about a late-eighteenth-century recipe for making fried chicken and how we ought to interpret it. Lawson’s pithy essay has much to be praised. Yet, even twenty-five years later, there remains more to be said about legal theory’s most famous recipe. In particular, there remains much more to be said about the recipe’s author, a person (or, perhaps, group of people) whom Lawson does not discuss. Lawson’s analysis of the recipe leads him to an “obvious” conclusion: the recipe’s meaning is its original public meaning. If we consider those who wrote the recipe and their joint act of recipe-writing, however, I question whether that conclusion remains so obvious. This Essay takes a closer look at the chefs who wrote the fried chicken recipe and their act of recipe-writing that produced it. I argue that the meaning of the fried chicken recipe is not its original public meaning but is rather the meaning the chefs intended the recipe to have, even on Lawson’s own terms
Protein modifications in baked versus fried tortilla chips
No full textLipid oxidation is recognized as the greatest problem in chemical stabilization of processed foods during storage. Lipid co-oxidations caused by reactions of lipid oxidation intermediates and products with other molecules, particularly proteins, are known, but their impact on food quality (production of off-flavors and odors, loss of color and nutritional value, and texture deterioration) remains largely unexplored, and relatively little is known about the mechanisms involved. However, it is likely that co-oxidations account for much of the “damage” normally attributed to lipid oxidation and provide footprints of lipid oxidation that are not detected in general assays of lipid oxidation. In this research, primary experiments have compared the difference between proteins in baked and fried tortilla chips to distinguish thermal effects of processing from co-oxidation by lipids. Preliminary results showed little difference in protein solubility in fresh baked or fried chips, yet gel electrophoresis revealed significant lipid-mediated differences in disulfide cross-linking in fried chips even immediately after processing without incubations. Schiff base formation was present, but only at low levels, indicating that it is not a major source of cross-linking in early stages of oxidation. Cross-linking continued to develop even more extensively in fried chips during storage at 40 and 60 ºC, and included free radical in addition to disulfide cross-linking. Western blots revealed the presence of protein carbonyls, important co-oxidation products, in most protein fractions in tortilla chips and notably in zeins. Surprisingly, more carbonyls were observed in baked chips with lower lipid content. To determine the connections between these protein changes and lipids, lipid oxidation is being followed in all systems by lipids extractability, free fatty acids, aldehydes and peroxides.M.S.Includes bibliographical referencesIncludes vitaby Yuan Don
A Scanning Tunneling Microscope with a Wide Sampling Range
No full textThis article may be downloaded for personal use only. Any other use requires prior permission of the author and AIP Publishing. This article appeared in Review of Scientific Instruments and may be found at https://aip.scitation.org/doi/10.1063/1.1141110.Construction of a simple scanning tunneling microscope (STM) is described. This STM is suitable for atmospheric, controlled atmosphere, and high vacuum (but not UHV) work. This STM is especially wen suited for determining surface topography on the 0.1 nm scale when images must be obtained over a wide sampling region (mm). Interchangeable piezo heads allow the STM to be used either for atomic resolution or for large (800 X 800 urn) area scans. Atomic resolution pictures of the graphite surface demonstrate that this design is suitable for use with structures smaller than 0.1 nm. An image of a thin film of Au, deposited on pyrex, is also presented.K.W. Hipps, Glenn Fried, and Dale Fried. (1990). A Scanning Tunneling Microscope with a Wide Sampling Range. Review of Scientific Instruments. 61 1869-1873
Negative stereotypes of the Scottish diet:A qualitative analysis of deep-fried Mars bar references in best selling newspapers in Scotland, 2011-14
No full textThe Scottish diet is associated in the UK media and popular discourse with unhealthy deep-fried foods. In addition to the stereotype’s negative effects on perceptions of Scottish food, culture and people, there is evidence that the stereotype of the Scottish diet has negative effects on food behaviour and public health in Scotland, having been shown to encourage consumption of deep-fried foods and discourage positive dietary change. The most notorious deep-fried food associated with Scotland is the deep-fried Mars bar (DFMB), arguably invented in Stonehaven (near Aberdeen), and first reported in the Scottish and UK press in 1995. This article reports findings from an analysis of newspaper references to the DFMB in the two highest selling newspapers in Scotland, the Scottish Sun and the Daily Record, between 2011 and 2014. A keyword search (“deep fried Mars bar”) using the online media database Lexis Library generated 97 unique records, and the resulting dataset was analysed thematically and discursively. Analysis showed that both newspapers clearly associated the DFMB with Scotland. Further, both newspapers portrayed the DFMB and the broader “deep-fried” Scottish diet stereotype ambivalently (mixed positive and negative associations). However, the Daily Record actively criticised the DFMB stereotype much more often than did the Scottish Sun. These findings suggest that the Scottish population encounters different messages in the press about food and nutrition from people elsewhere in the UK, and that these messages vary depending on choice of media in Scotland. Given the known negative effects of the stereotype, differences in Scottish media discourse should be considered a potential factor in persistent health inequalities affecting Scotland. Educational efforts, and opening discussion with journalists and amongst the Scottish public, may be helpful
- …
