bluuebunny/crossref_metadata_2025_split huggingface dataset:
Automated lemma synthesis in symbolic-heap separation logic
Authors: Ta Quang-Trung , Le Ton Chanh , Khoo Siau-Cheng , Chin Wei-Ngan 
Published: December 2017

The symbolic-heap fragment of separation logic has been actively developed and advocated for verifying the memory-safety property of computer programs. At present, one of its biggest challenges is to effectively prove entailments containing inductive heap predicates. These entailments are usually proof obligations generated when verifying programs that manipulate complex data structures like linked lists, trees, or graphs.
To assist in proving such entailments, this paper introduces a lemma synthesis framework, which automatically discovers lemmas to serve as eureka steps in the proofs. Mathematical induction and template-based constraint solving are two pillars of our framework. To derive the supporting lemmas for a given entailment, the framework firstly identifies possible lemma templates from the entailment's heap structure. It then sets up unknown relations among each template's variables and conducts structural induction proof to generate constraints about these relations. Finally, it solves the constraints to find out actual definitions of the unknown relations, thus discovers the lemmas. We have integrated this framework into a prototype prover and have experimented it on various entailment benchmarks. The experimental results show that our lemma-synthesis-assisted prover can prove many entailments that could not be handled by existing techniques. This new proposal opens up more opportunities to automatically reason with complex inductive heap predicates.
Jones-optimal partial evaluation by specialization-safe normalization
Authors: Brown Matt , Palsberg Jens 
Published: December 2017

We present partial evaluation by specialization-safe normalization, a novel partial evaluation technique that is Jones-optimal, that can be self-applied to achieve the Futamura projections and that can be type-checked to ensure it always generates code with the correct type. Jones-optimality is the gold-standard for nontrivial partial evaluation and guarantees that a specializer can remove an entire layer of interpretation. We achieve Jones-optimality by using a novel affine-variable static analysis that directs specialization-safe normalization to always decrease a program’s runtime.
We demonstrate the robustness of our approach by showing Jones-optimality in a variety of settings. We have formally proved that our partial evaluator is Jones-optimal for call-by-value reduction, and we have experimentally shown that it is Jones-optimal for call-by-value, normal-order, and memoized normal-order. Each of our experiments tests Jones-optimality with three different self-interpreters.

We implemented our partial evaluator in F
ω

µ
i

, a recent language for typed self-applicable meta-programming. It is the first Jones-optimal and self-applicable partial evaluator whose type guarantees that it always generates type-correct code.
Migrating gradual types
Authors: Campora John Peter , Chen Sheng , Erwig Martin , Walkingshaw Eric 
Published: December 2017

Gradual typing allows programs to enjoy the benefits of both static typing and dynamic typing. While it is often desirable to migrate a program from more dynamically-typed to more statically-typed or vice versa, gradual typing itself does not provide a way to facilitate this migration. This places the burden on programmers who have to manually add or remove type annotations. Besides the general challenge of adding type annotations to dynamically typed code, there are subtle interactions between these annotations in gradually typed code that exacerbate the situation. For example, to migrate a program to be as static as possible, in general, all possible combinations of adding or removing type annotations from parameters must be tried out and compared.
In this paper, we address this problem by developing migrational typing, which efficiently types all possible ways of adding or removing type annotations from a gradually typed program. The typing result supports automatically migrating a program to be as static as possible, or introducing the least number of dynamic types necessary to remove a type error. The approach can be extended to support user-defined criteria about which annotations to modify. We have implemented migrational typing and evaluated it on large programs. The results show that migrational typing scales linearly with the size of the program and takes only 2–4 times longer than plain gradual typing.
Progress of concurrent objects with partial methods
Authors: Liang Hongjin , Feng Xinyu 
Published: December 2017

Various progress properties have been proposed for concurrent objects, such as wait-freedom, lock-freedom, starvation-freedom and deadlock-freedom. However, none of them applies to concurrent objects with partial methods, i.e., methods that are supposed not to return under certain circumstances. A typical example is the lock_acquire method, which must not return when the lock has already been acquired.
In this paper we propose two new progress properties, partial starvation-freedom (PSF) and partial deadlock-freedom (PDF), for concurrent objects with partial methods. We also design four patterns to write abstract specifications for PSF or PDF objects under strongly or weakly fair scheduling, so that these objects contextually refine the abstract specifications. Our Abstraction Theorem shows the equivalence between PSF (or PDF) and the progress-aware contextual refinement. Finally, we generalize the program logic LiLi to have a new logic to verify the PSF (or PDF) property and linearizability of concurrent objects.
Safety and conservativity of definitions in HOL and Isabelle/HOL
Authors: Kunčar Ondřej , Popescu Andrei 
Published: December 2017

Definitions are traditionally considered to be a safe mechanism for introducing concepts on top of a logic known to be consistent. In contrast to arbitrary axioms, definitions should in principle be treatable as a form of abbreviation, and thus compiled away from the theory without losing provability. In particular, definitions should form a conservative extension of the pure logic. These properties are crucial for modern interactive theorem provers, since they ensure the consistency of the logic, as well as a valid environment for total/certified functional programming.
We prove these properties, namely, safety and conservativity, for Higher-Order Logic (HOL), a logic implemented in several mainstream theorem provers and relied upon by thousands of users. Some unique features of HOL, such as the requirement to give non-emptiness proofs when defining new types and the impossibility to unfold type definitions, make the proof of these properties, and also the very formulation of safety, nontrivial.
Our study also factors in the essential variation of HOL definitions featured by Isabelle/HOL, a popular member of the HOL-based provers family. The current work improves on recent results which showed a weaker property, consistency of Isabelle/HOL's definitions.
Reducing liveness to safety in first-order logic
Authors: Padon Oded , Hoenicke Jochen , Losa Giuliano , Podelski Andreas , Sagiv Mooly , Shoham Sharon 
Published: December 2017

We develop a new technique for verifying temporal properties of infinite-state (distributed) systems. The main idea is to reduce the temporal verification problem to the problem of verifying the safety of infinite-state systems expressed in first-order logic. This allows to leverage existing techniques for safety verification to verify temporal properties of interesting distributed protocols, including some that have not been mechanically verified before. We model infinite-state systems using first-order logic, and use first-order temporal logic (FO-LTL) to specify temporal properties. This general formalism allows to naturally model distributed systems, while supporting both unbounded-parallelism (where the system is allowed to dynamically create processes), and infinite-state per process.
The traditional approach for verifying temporal properties of infinite-state systems employs well-founded relations (e.g. using linear arithmetic ranking functions). In contrast, our approach is based the idea of fair cycle detection. In finite-state systems, temporal verification can always be reduced to fair cycle detection (a system contains a fair cycle if it revisits a state after satisfying all fairness constraints). However, with both infinitely many states and infinitely many fairness constraints, a straightforward reduction to fair cycle detection is unsound. To regain soundness, we augment the infinite-state transition system by a dynamically computed finite set, that exploits the locality of transitions. This set lets us define a form of fair cycle detection that is sound in the presence of both infinitely many states, and infinitely many fairness constraints. Our approach allows a new style of temporal verification that does not explicitly involve ranking functions. This fits well with pure first-order verification which does not explicitly reason about numerical values. In particular, it can be used with effectively propositional first-order logic (EPR), in which case checking verification conditions is decidable. We applied our technique to verify temporal properties of several interesting protocols. To the best of our knowledge, we have obtained the first mechanized liveness proof for both TLB Shootdown, and Stoppable Paxos.
Why is random testing effective for partition tolerance bugs?
Authors: Majumdar Rupak , Niksic Filip 
Published: December 2017

Random testing has proven to be an effective way to catch bugs in distributed systems in the presence of network partition faults. This is surprising, as the space of potentially faulty executions is enormous, and the bugs depend on a subtle interplay between sequences of operations and faults.
We provide a theoretical justification of the effectiveness of random testing in this context. First, we show a general construction, using the probabilistic method from combinatorics, that shows that whenever a random test covers a fixed coverage goal with sufficiently high probability, a small randomly-chosen set of tests achieves full coverage with high probability. In particular, we show that our construction can give test sets exponentially smaller than systematic enumeration. Second, based on an empirical study of many bugs found by random testing in production distributed systems, we introduce notions of test coverage relating to network partition faults which are effective in finding bugs. Finally, we show using combinatorial arguments that for these notions of test coverage we introduce, we can find a lower bound on the probability that a random test covers a given goal. Our general construction then explains why random testing tools achieve good coverage---and hence, find bugs---quickly.
While we formulate our results in terms of network partition faults, our construction provides a step towards rigorous analysis of random testing algorithms, and can be applicable in other scenarios.
Non-linear reasoning for invariant synthesis
Authors: Kincaid Zachary , Cyphert John , Breck Jason , Reps Thomas 
Published: December 2017

Automatic generation of non-linear loop invariants is a long-standing challenge in program analysis, with many applications. For instance, reasoning about exponentials provides a way to find invariants of digital-filter programs, and reasoning about polynomials and/or logarithms is needed for establishing invariants that describe the time or memory usage of many well-known algorithms. An appealing approach to this challenge is to exploit the powerful recurrence-solving techniques that have been developed in the field of computer algebra, which can compute exact characterizations of non-linear repetitive behavior. However, there is a gap between the capabilities of recurrence solvers and the needs of program analysis: (1) loop bodies are not merely systems of recurrence relations---they may contain conditional branches, nested loops, non-deterministic assignments, etc., and (2) a client program analyzer must be able to reason about the closed-form solutions produced by a recurrence solver (e.g., to prove assertions).
This paper presents a method for generating non-linear invariants of general loops based on analyzing recurrence relations. The key components are an abstract domain for reasoning about non-linear arithmetic, a semantics-based method for extracting recurrence relations from loop bodies, and a recurrence solver that avoids closed forms that involve complex or irrational numbers. Our technique has been implemented in a program analyzer that can analyze general loops and mutually recursive procedures. Our experiments show that our technique shows promise for non-linear assertion-checking and resource-bound generation.
Proving expected sensitivity of probabilistic programs
Authors: Barthe Gilles , Espitau Thomas , Grégoire Benjamin , Hsu Justin , Strub Pierre-Yves 
Published: December 2017

Program sensitivity, also known as Lipschitz continuity, describes how small changes in a program’s input lead to bounded changes in the output. We propose an average notion of program sensitivity for probabilistic programs—expected sensitivity—that averages a distance function over a probabilistic coupling of two output distributions from two similar inputs. By varying the distance, expected sensitivity recovers useful notions of probabilistic function sensitivity, including stability of machine learning algorithms and convergence of Markov chains.
Furthermore, expected sensitivity satisfies clean compositional properties and is amenable to formal verification. We develop a relational program logic called EpRHL for proving expected sensitivity properties. Our logic features two key ideas. First, relational pre-conditions and post-conditions are expressed using distances, a real-valued generalization of typical boolean-valued (relational) assertions. Second, judgments are interpreted in terms of expectation coupling, a novel, quantitative generalization of probabilistic couplings which supports compositional reasoning.
We demonstrate our logic on examples beyond the reach of prior relational logics. Our main example formalizes uniform stability of the stochastic gradient method. Furthermore, we prove rapid mixing for a probabilistic model of population dynamics. We also extend our logic with a transitivity principle for expectation couplings to capture the path coupling proof technique by Bubley and Dyer, and formalize rapid mixing of the Glauber dynamics from statistical physics.
Recalling a witness: foundations and applications of monotonic state
Authors: Ahman Danel , Fournet Cédric , Hriţcu Cătălin , Maillard Kenji , Rastogi Aseem , Swamy Nikhil 
Published: December 2017

We provide a way to ease the verification of programs whose state evolves monotonically. The main idea is that a property
witnessed
in a prior state can be soundly
recalled
in the current state, provided (1) state evolves according to a given preorder, and (2) the property is preserved by this preorder. In many scenarios, such monotonic reasoning yields concise modular proofs, saving the need for explicit program invariants. We distill our approach into the
monotonic-state monad
, a general yet compact interface for Hoare-style reasoning about monotonic state in a dependently typed language. We prove the soundness of the monotonic-state monad and use it as a unified foundation for reasoning about monotonic state in the F
⋆
verification system. Based on this foundation, we build libraries for various mutable data structures like monotonic references and apply these libraries at scale to the verification of several distributed applications.
ПОРІВНЯЛЬНИЙ АНАЛІЗ ПРОФЕСІЙНОЇ ПІДГОТОВКИ СТУДЕНТІВ І КУРСУ СПЕЦІАЛЬНОСТІ «ФАРМАЦІЯ» В УКРАЇНІ ТА НІМЕЧЧИНІ
Authors: Goroshko О. М. , Korovenkova О. M. , Palamar А. О. , Bogdan N. S. , Rovinskyi О. О. , Zeleniuk V. H. , Shpychak O. S. 
Published: December 2017

Мета роботи. Вивчення процесу ознайомлення студентів І курсу фармацевтичних факультетів з майбутньою спеціальністю у вищому навчальному закладі (ВНЗ) порівняно з аналогічним курсом Боннського університету (Німеччина).Матеріали і методи. Використано нормативно-правову базу, що регулює освітній процес в Україні та Німеччині: проведено аналіз організації підготовки студентів фармацевтичних факультетів. Для порівняльного аналізу обрано фармацевтичний факультет Боннського університету (Німеччина).Результати й обговорення. Встановлено, що відмінності у дисциплінах, які дають можливість ознайомити студентів-магістрів із майбутньою спеціальністю, є незначними, а саме більше теоретичного матеріалу, що можна пояснити відносно молодим періодом становлення фармації в Україні. Перевагою у підготовці вітчизняних студентів є проходження практичної підготовки на базі навчально-виробничої аптеки, що сприяє адаптації майбутніх випускників на робочому місці.Висновки. Дисципліна «Вступ у фармацію» забезпечує ознайомлення першокурсників фармацевтичних факультетів з особливостями фармацевтичної справи аналогічно як і в європейському університеті м. Бонн (Німеччина) під час вивчення курсу «Arzneimittelformenlehre».
The Aetiological Myth of the Russian Empire and the Study in Russia of Cultural Changes in the North Pontic Region from the 3rd Century bc to the 3rd Century ad (Prior to the 1920s)
Authors: Mordvintseva Valentina I. 
Published: December 2017

Abstract
Cultural change in the “barbarian” world of the North Pontic region from the 3rd century bc to the mid-3rd century ad was not a special field of interest for ancient authors. Classical narratives only contain information about certain manifestations of such processes. In Russia, interest in studying the cultural changes that took place in the steppes of Eastern Europe in Antiquity appeared in the early 18th century, in connection with the accession of new territories to the East and West. The core of the cultural-historical model, which took shape and then developed in Russian historical research, was the idea of a constantly changing succession of peoples in the North Pontic region and of the historical role of this region as a buffer zone between East and West. On this basis, an aetiological myth of the Russian Empire took root, justifying its impressive size, its length along the meta-geographical axis of Eurasia and its historic role in the destiny of Europe. This concept assumed its definitive form in the early 20th century in the works of Mikhail Rostovtsev.
The Peculiarities of the Geographical Distribution of the Pazyryk Kurgans
Authors: Ochir-Goryaeva Maria 
Published: December 2017

Abstract
The article proposes a division of the Pazyryk culture sites from the steppe valleys of the mountain Altai according to landscape-and-geographical principle − along the Katun-Chuya ridge into west and east habitats. A review of basic sites within the limits of the two habitats revealed differences in their number, location and burial inventory, confirming the existence of the two habitats.
Occupational therapy private practice workforce: Issues in the 21st century
Authors: Kobbero Tiffany K. , Lynch Catherine H. , Boniface Giovanna , Forwell Susan J. 
Published: December 2017

Background. The number of occupational therapists working in the private sector in British Columbia (BC) has risen steadily since 2008, employing approximately 25.7% of occupational therapists by 2012. Processes used to determine workforce needs for occupational therapists in BC have previously overlooked this growing sector. Purpose. This study aims to describe the supply, demand, and workforce needs for occupational therapists in BC’s private sector. Method. This exploratory study used a sample of occupational therapists and employers of occupational therapists in BC’s private sector. Data collection included an online survey that collected information about the workplace and supply and demand needs. Descriptive data analysis was conducted on the survey data, and thematic analysis was used to organize participants’ comments into categories. Findings. In addition to identifying current supply, this study identifies barriers, facilitators, projected movement in and out of the sector, and current and future demand for occupational therapists. Implications. This study supports the need for an increase in supply of occupational therapists in the private sector to fulfill the current and future workforce demands.
State-dependent alterations of lipid profiles in patients with bipolar disorder
Authors: Huang Yu-Jui , Tsai Shang-Ying , Chung Kuo-Hsuan , Chen Pao-Huan , Huang Shou-Hung , Kuo Chian-Jue 
Published: December 2017

Objective Serum lipid levels may be associated with the affective severity of bipolar disorder, but data on lipid profiles in Asian patients with bipolar disorder and the lipid alterations in different states of opposite polarities are scant. We investigated the lipid profiles of patients in the acute affective, partial, and full remission state in bipolar mania and depression. Methods The physically healthy patients aged between 18 and 45 years with bipolar I disorder, as well as age-matched healthy normal controls were enrolled. We compared the fasting blood levels of glucose, cholesterol, triglyceride, low-density lipoprotein, and high-density lipoprotein of manic or depressed patients in the acute phase and subsequent partial and full remission with those of their normal controls. Results A total of 32 bipolar manic patients (12 women and 20 men), 32 bipolar depressed participants (18 women and 14 men), and 64 healthy control participants took part in this study. The mean cholesterol level in acute mania was significantly lower than that in acute depression (p < 0.025). The lowest rate of dyslipidemia (hypertriglyceridemia or low high-density lipoprotein cholesterol) was observed in acute bipolar mania. Conclusion Circulating lipid profiles may be easily affected by affective states. The acute manic state may be accompanied by state-dependent lower cholesterol and triglyceride levels relative to that in other mood states.