TY - CONF AB - Safety and liveness are elementary concepts of computation, and the foundation of many verification paradigms. The safety-liveness classification of boolean properties characterizes whether a given property can be falsified by observing a finite prefix of an infinite computation trace (always for safety, never for liveness). In quantitative specification and verification, properties assign not truth values, but quantitative values to infinite traces (e.g., a cost, or the distance to a boolean property). We introduce quantitative safety and liveness, and we prove that our definitions induce conservative quantitative generalizations of both (1)~the safety-progress hierarchy of boolean properties and (2)~the safety-liveness decomposition of boolean properties. In particular, we show that every quantitative property can be written as the pointwise minimum of a quantitative safety property and a quantitative liveness property. Consequently, like boolean properties, also quantitative properties can be min-decomposed into safety and liveness parts, or alternatively, max-decomposed into co-safety and co-liveness parts. Moreover, quantitative properties can be approximated naturally. We prove that every quantitative property that has both safe and co-safe approximations can be monitored arbitrarily precisely by a monitor that uses only a finite number of states. AU - Henzinger, Thomas A AU - Mazzocchi, Nicolas Adrien AU - Sarac, Naci E ID - 12467 SN - 0302-9743 T2 - 26th International Conference Foundations of Software Science and Computation Structures TI - Quantitative safety and liveness VL - 13992 ER - TY - JOUR AB - Writing concurrent code that is both correct and efficient is notoriously difficult. Thus, programmers often prefer to use synchronization abstractions, which render code simpler and easier to reason about. Despite a wealth of work on this topic, there is still a gap between the rich semantics provided by synchronization abstractions in modern programming languages—specifically, fair FIFO ordering of synchronization requests and support for abortable operations—and frameworks for implementing it correctly and efficiently. Supporting such semantics is critical given the rising popularity of constructs for asynchronous programming, such as coroutines, which abort frequently and are cheaper to suspend and resume compared to native threads. This paper introduces a new framework called CancellableQueueSynchronizer (CQS), which enables simple yet efficient implementations of a wide range of fair and abortable synchronization primitives: mutexes, semaphores, barriers, count-down latches, and blocking pools. Our main contribution is algorithmic, as implementing both fairness and abortability efficiently at this level of generality is non-trivial. Importantly, all our algorithms, including the CQS framework and the primitives built on top of it, come with formal proofs in the Iris framework for Coq for many of their properties. These proofs are modular, so it is easy to show correctness for new primitives implemented on top of CQS. From a practical perspective, implementation of CQS for native threads on the JVM improves throughput by up to two orders of magnitude over Java’s AbstractQueuedSynchronizer, the only practical abstraction offering similar semantics. Further, we successfully integrated CQS as a core component of the popular Kotlin Coroutines library, validating the framework’s practical impact and expressiveness in a real-world environment. In sum, CancellableQueueSynchronizer is the first framework to combine expressiveness with formal guarantees and solid practical performance. Our approach should be extensible to other languages and families of synchronization primitives. AU - Koval, Nikita AU - Khalanskiy, Dmitry AU - Alistarh, Dan-Adrian ID - 13179 JF - Proceedings of the ACM on Programming Languages TI - CQS: A formally-verified framework for fair and abortable synchronization VL - 7 ER - TY - JOUR AB - We study the density of everywhere locally soluble diagonal quadric surfaces, parameterised by rational points that lie on a split quadric surface AU - Browning, Timothy D AU - Lyczak, Julian AU - Sarapin, Roman ID - 13180 IS - 2 JF - Involve SN - 1944-4176 TI - Local solubility for a family of quadrics over a split quadric surface VL - 16 ER - TY - GEN AU - Elefante, Stefano AU - Stadlbauer, Stephan AU - Alexander, Michael F AU - Schlögl, Alois ID - 13162 T2 - ASHPC23 - Austrian-Slovenian HPC Meeting 2023 TI - Cryo-EM software packages: A sys-admins point of view ER - TY - GEN AU - Schlögl, Alois AU - Elefante, Stefano AU - Hodirnau, Victor-Valentin ID - 13161 T2 - ASHPC23 - Austrian-Slovenian HPC Meeting 2023 TI - Running Windows-applications on a Linux HPC cluster using WINE ER - TY - JOUR AB - A rotating organic cation and a dynamically disordered soft inorganic cage are the hallmark features of organic-inorganic lead-halide perovskites. Understanding the interplay between these two subsystems is a challenging problem, but it is this coupling that is widely conjectured to be responsible for the unique behavior of photocarriers in these materials. In this work, we use the fact that the polarizability of the organic cation strongly depends on the ambient electrostatic environment to put the molecule forward as a sensitive probe of the local crystal fields inside the lattice cell. We measure the average polarizability of the C/N–H bond stretching mode by means of infrared spectroscopy, which allows us to deduce the character of the motion of the cation molecule, find the magnitude of the local crystal field, and place an estimate on the strength of the hydrogen bond between the hydrogen and halide atoms. Our results pave the way for understanding electric fields in lead-halide perovskites using infrared bond spectroscopy. AU - Wei, Yujing AU - Volosniev, Artem AU - Lorenc, Dusan AU - Zhumekenov, Ayan A. AU - Bakr, Osman M. AU - Lemeshko, Mikhail AU - Alpichshev, Zhanybek ID - 13251 IS - 27 JF - The Journal of Physical Chemistry Letters KW - General Materials Science KW - Physical and Theoretical Chemistry TI - Bond polarizability as a probe of local crystal fields in hybrid lead-halide perovskites VL - 14 ER - TY - CONF AB - The operator precedence languages (OPLs) represent the largest known subclass of the context-free languages which enjoys all desirable closure and decidability properties. This includes the decidability of language inclusion, which is the ultimate verification problem. Operator precedence grammars, automata, and logics have been investigated and used, for example, to verify programs with arithmetic expressions and exceptions (both of which are deterministic pushdown but lie outside the scope of the visibly pushdown languages). In this paper, we complete the picture and give, for the first time, an algebraic characterization of the class of OPLs in the form of a syntactic congruence that has finitely many equivalence classes exactly for the operator precedence languages. This is a generalization of the celebrated Myhill-Nerode theorem for the regular languages to OPLs. As one of the consequences, we show that universality and language inclusion for nondeterministic operator precedence automata can be solved by an antichain algorithm. Antichain algorithms avoid determinization and complementation through an explicit subset construction, by leveraging a quasi-order on words, which allows the pruning of the search space for counterexample words without sacrificing completeness. Antichain algorithms can be implemented symbolically, and these implementations are today the best-performing algorithms in practice for the inclusion of finite automata. We give a generic construction of the quasi-order needed for antichain algorithms from a finite syntactic congruence. This yields the first antichain algorithm for OPLs, an algorithm that solves the ExpTime-hard language inclusion problem for OPLs in exponential time. AU - Henzinger, Thomas A AU - Kebis, Pavol AU - Mazzocchi, Nicolas Adrien AU - Sarac, Naci E ID - 13292 SN - 9783959772785 T2 - 50th International Colloquium on Automata, Languages, and Programming TI - Regular methods for operator precedence languages VL - 261 ER - TY - JOUR AB - Recent experimental advances have inspired the development of theoretical tools to describe the non-equilibrium dynamics of quantum systems. Among them an exact representation of quantum spin systems in terms of classical stochastic processes has been proposed. Here we provide first steps towards the extension of this stochastic approach to bosonic systems by considering the one-dimensional quantum quartic oscillator. We show how to exactly parameterize the time evolution of this prototypical model via the dynamics of a set of classical variables. We interpret these variables as stochastic processes, which allows us to propose a novel way to numerically simulate the time evolution of the system. We benchmark our findings by considering analytically solvable limits and providing alternative derivations of known results. AU - Tucci, Gennaro AU - De Nicola, Stefano AU - Wald, Sascha AU - Gambassi, Andrea ID - 13277 IS - 2 JF - SciPost Physics Core KW - Statistical and Nonlinear Physics KW - Atomic and Molecular Physics KW - and Optics KW - Nuclear and High Energy Physics KW - Condensed Matter Physics SN - 2666-9366 TI - Stochastic representation of the quantum quartic oscillator VL - 6 ER - TY - JOUR AB - We introduce a generic and accessible implementation of an exact diagonalization method for studying few-fermion models. Our aim is to provide a testbed for the newcomers to the field as well as a stepping stone for trying out novel optimizations and approximations. This userguide consists of a description of the algorithm, and several examples in varying orders of sophistication. In particular, we exemplify our routine using an effective-interaction approach that fixes the low-energy physics. We benchmark this approach against the existing data, and show that it is able to deliver state-of-the-art numerical results at a significantly reduced computational cost. AU - Rammelmüller, Lukas AU - Huber, David AU - Volosniev, Artem ID - 13276 JF - SciPost Physics Codebases SN - 2949-804X TI - A modular implementation of an effective interaction approach for harmonically trapped fermions in 1D ER - TY - GEN AB - We introduce a generic and accessible implementation of an exact diagonalization method for studying few-fermion models. Our aim is to provide a testbed for the newcomers to the field as well as a stepping stone for trying out novel optimizations and approximations. This userguide consists of a description of the algorithm, and several examples in varying orders of sophistication. In particular, we exemplify our routine using an effective-interaction approach that fixes the low-energy physics. We benchmark this approach against the existing data, and show that it is able to deliver state-of-the-art numerical results at a significantly reduced computational cost. AU - Rammelmüller, Lukas AU - Huber, David AU - Volosniev, Artem ID - 13275 TI - Codebase release 1.0 for FermiFCI ER -