bluuebunny/crossref_metadata_2025 huggingface dataset:
Ten‐year functional and oncological outcomes of a prospective randomized controlled trial comparing laparoscopic versus robot‐assisted radical prostatectomy
Authors: Checcucci Enrico , De Cillis Sabrina , Alladio Eugenio , Piramide Federico , Volpi Gabriele , Granato Stefano , Zamengo Davide , Bignante Gabriele , Amparore Daniele , Piana Alberto , Manfredi Matteo , Vallariello Edoardo , Stura Ilaria , Di Dio Michele , Autorino Riccardo , Porpiglia Francesco , Fiori Cristian
Published: April 2024

Background

Among prostate cancer (PCa) treatment options, mini‐invasive surgical approaches have gained a wide diffusion in the last decades. The aim of this study was to present oncological, functional, and quality of life data after 10 years of follow‐up of a prospective randomized controlled trial (RCT) (ISRCTN11552140) comparing robot‐assisted radical prostatectomy (RARP) versus laparoscopic radical prostatectomy (LRP) for the treatment of PCa.

Methods

Patients with localized PCa were randomized to undergo LRP or RARP between January 2010 and January 2011. Functional (continence and potency) and oncological (prostate‐specific antigen, biochemical recurrence [BCR] and BCR‐free survival [BCRFS]) variables were evaluated. BCRFS curves were estimated by the Kaplan–Meier method and compared using the log‐rank test. Machine learning partial least square‐discriminant analysis (PLS‐DA) was used to identify the variables characterizing more the patients who underwent RARP or LRP.

Results

Seventy‐five of the originally enrolled 120 patients remained on follow‐up for 10 years; 40 (53%) underwent RARP and 35 (47%) LRP. Continence and potency recovery rates did not show significant differences (p = 0.068 and p = 0.56, respectively), despite a Δ12% for continence and Δ8% for potency in favor of the robotic approach. However, the quality of continence (in terms of International Consultation on Incontinence Questionnaire‐Short Form [ICIQ‐SF] score) and erection (in terms of International Index of Erectile Function‐5 [IIEF‐5] score) was significantly better after 10 years in the robotic group (p = 0.02 and p < 0.001). PLS‐DA revealed that LRP was characterized by the worst functional‐related outcomes analyzing the entire follow‐up period. Four (10%) and six (17%) patients experienced BCR in RARP and LRP groups, respectively (p = 0.36), with an overall 10‐year BCR‐free survival of 88% and 78% (p = 0.16).

Conclusions

Comparable continence and potency rates were observed between RARP and LRP after a 10‐year follow‐up. However, the RARP group exhibited superior totally dry rate and erection quality. No difference in terms of oncological outcomes was found.
Beyond the two‐trials rule
Authors: Held Leonhard
Published: April 2024

The two‐trials rule for drug approval requires “at least two adequate and well‐controlled studies, each convincing on its own, to establish effectiveness.” This is usually implemented by requiring two significant pivotal trials and is the standard regulatory requirement to provide evidence for a new drug's efficacy. However, there is need to develop suitable alternatives to this rule for a number of reasons, including the possible availability of data from more than two trials. I consider the case of up to three studies and stress the importance to control the partial Type‐I error rate, where only some studies have a true null effect, while maintaining the overall Type‐I error rate of the two‐trials rule, where all studies have a null effect. Some less‐known ‐value combination methods are useful to achieve this: Pearson's method, Edgington's method and the recently proposed harmonic mean ‐test. I study their properties and discuss how they can be extended to a sequential assessment of success while still ensuring overall Type‐I error control. I compare the different methods in terms of partial Type‐I error rate, project power and the expected number of studies required. Edgington's method is eventually recommended as it is easy to implement and communicate, has only moderate partial Type‐I error rate inflation but substantially increased project power.
Engineering Material Properties of Transcription Factor Condensates to Control Gene Expression in Mammalian Cells and Mice
Authors: Fischer Alexandra A.M. , Robertson Hanah B. , Kong Deqiang , Grimm Merlin M. , Grether Jakob , Groth Johanna , Baltes Carsten , Fliegauf Manfred , Lautenschläger Franziska , Grimbacher Bodo , Ye Haifeng , Helms Volkhard , Weber Wilfried
Published: April 2024

Phase separation of biomolecules into condensates is a key mechanism in the spatiotemporal organization of biochemical processes in cells. However, the impact of the material properties of biomolecular condensates on important processes, such as the control of gene expression, remains largely elusive. Here, the material properties of optogenetically induced transcription factor condensates are systematically tuned, and probed for their impact on the activation of target promoters. It is demonstrated that transcription factors in rather liquid condensates correlate with increased gene expression levels, whereas stiffer transcription factor condensates correlate with the opposite effect, reduced activation of gene expression. The broad nature of these findings is demonstrated in mammalian cells and mice, as well as by using different synthetic and natural transcription factors. These effects are observed for both transgenic and cell‐endogenous promoters. The findings provide a novel materials‐based layer in the control of gene expression, which opens novel opportunities in optogenetic engineering and synthetic biology.
Facile Magnetite Coating for Stable High‐Voltage Cycling of Nickel‐Rich Cathodes in Conventional Liquid and All‐Solid‐State Lithium‐Ion Batteries
Authors: Mahajani Varad , Bhimani Kevin , Lakhnot Aniruddha Singh , Panchal Reena , Anjan Apurva , Manoj Rohit M. , Koratkar Nikhil
Published: April 2024

The instability of Nickel (Ni)‐rich cathodes at high voltage is a critical bottleneck toward developing superior lithium‐ion batteries. This instability is driven by cathode‐electrolyte side reactions, causing rapid degradation, and compromising the overall cycle life. In this study, a protective coating using dispersed “magnetite (FeO.Fe2O3)” nanoparticles is used to uniformly decorate the surface of LiNi0.8Co0.1Mn0.1O2 (NMC 811) microparticles. The modified cathode delivers significant improvement in electrochemical performance at high voltage (≈4.6 V) by suppressing deleterious electrode–electrolyte interactions. A notably higher cycle stability, rate performance, and overall energy density is realized for the coated cathode in a conventional liquid electrolyte battery. When deployed in pellet‐stacked solid‐state cells with Li6PS5Cl as the electrolyte, the magnetite‐coated NMC 811 showed strikingly superior cycling stability than its uncoated counterpart, proving the versatility of the chemistry. The facile surfactant‐assisted coating process developed in this work, in conjunction with the affordability, abundance, and nontoxic nature of magnetite makes this a promising approach to realize commercially viable high voltage Ni‐rich cathodes that exhibit stable performance in liquid as well as solid‐state lithium‐ion batteries.
Separating insider and informed behavior: Evidence from a natural setting
Authors: Hegarty Tadgh
Published: April 2024

Previous literature has established the need to separate insider from expert trading in both financial and betting markets. This type of separation proves difficult to achieve because experts and insiders co‐exist in most market settings. Utilizing novel betting markets in which expert skill bettors are unable to use their expert knowledge, this study uncouples insider from expert betting, and allows more direct measurement of insider trading than in previous empirical tests. Evidence is presented in favor of some predictions from the highly cited Shin model of insider trading. Price setters charge an extra premium in markets with high proportions of insiders when compared to equivalent markets. The insiders accurately predict event outcomes, and their presence exacerbates a well known bias in betting market prices whereby returns on betting favorites is higher than for bets on longshots.
Does capitalism disfavor women? Evidence from life satisfaction
Authors: Berggren Niclas , Bjørnskov Christian
Published: April 2024

There is concern, especially in certain feminist circles, that capitalism disfavors women. This could take many forms, for example, lower wages for the same work, reduced career opportunities, disparities in ownership, and the upholding of traditional gender roles, and it could result in capitalism conferring more life satisfaction on men than on women. We test empirically whether this concern is justified. Using the epidemiological approach to rule out reverse causality, we first confirm previous findings that most areas of economic freedom (legal quality in particular, but also monetary stability, openness, and regulation) are beneficial for general life satisfaction. When looking at women and men separately, we find virtually no statistically significant differences, and in the cases we do, the estimates reveal a more beneficial outcome for women. Hence, we conclude that capitalism does not seem to favor men more than women in terms of life satisfaction.
Analysis and Selection of Optimal Perovskite/Silicon Tandem Configuration for Building Integrated Photovoltaics Based on Their Annual Outdoor Energy Yield Predicted by Machine Learning
Authors: Nguyen Dong C. , Asada Tomoki , Raifuku Itaru , Ishikawa Yasuaki
Published: April 2024

Accurate estimation of annual output energy yield () for perovskite/silicon (PSK/cSi) tandem solar cells is pivotal in assessing their suitability for building‐integrated photovoltaics (BIPV). This study pioneers five machine learning models of ensembles of trees, Gaussian process regressions, regression trees, support vector machines, and artificial neural networks (ANN) to predict output power density and compute for 2T, 3T, and 4T PSK/cSi tandem configurations in Japan's outdoor conditions. Seven predictive inputs of visible‐light solar irradiance, near‐infrared‐light solar irradiance, incident solar spectrum angle, solar module temperature, perovskite thickness, perovskite bandgap, and terminal of tandem configuration (T) drive the machine learning models. These models optimize predictions using k‐fold cross‐validation and Bayesian algorithms, showcasing superior precision in prediction compared to prior models. The ANN model emerges as the best model, displaying the minimal error in predicting , used to estimate across five Japanese locations (Gifu, Naganuma, Okinoerabu, Tosu, and Tsukuba). Results from these locations in blue‐rich solar spectrum zones identify the 4T PSK/cSi tandem configuration, featuring the most outstanding mean maximal (93.63, 263.02, 153.59, and 91.75 kWh m−2 for the east, rooftop, south, and west directions), as the prime candidate for BIPV applications.
Characterization of Starch Properties in Diverse Pea Accessions: Structural, Morphological, Thermal, Pasting, and Retrogradation Analysis
Authors: Shevkani Khetan , Singh Narpinder , Kaur Navpreet , Isono Naoto , Noda Takahiro
Published: April 2024

The present work evaluates starch from 29 diverse pea accessions for structural (amylose content and amylopectin chain length distribution), granule size distribution, thermal, pasting, and retrogradation properties. Amylose content and the proportion of amylopectin chains with the degree of polymerization (DP) of 6–10, 11–20, and >20 vary in the range from 21.4% to 57.0%, 17.9% to 25.8%, 64.0% to 66.5%, and 9.4% to 16.7%, respectively. Starches with a higher proportion of small granules (<5 µm) have a greater proportion of amylopectin chains with DP > 10 and exhibit higher transition temperatures/enthalpy and vice versa. Retrogradation in starch pastes relates negatively to the proportion of amylopectin chains with DP < 10. Paste viscosities relate negatively with amylopectin chains with DP > 10, amylose content, and retrogradation while positively with transition temperatures/enthalpy and the potential of granules to swell.
Single‐cell transcriptome sequencing analysis reveals intra‐tumor heterogeneity in esophageal squamous cell carcinoma
Authors: Nie Yuanliu , Yao Guangyue , Wei Yanjun , Wu Sheng , Zhang Wentao , Xu Xiaoying , Li Qiang , Zhou Fengge , Yang Zhe
Published: April 2024

Esophageal squamous cell carcinoma (ESCC) is a prevalent malignant tumor of the digestive system that poses a significant threat to human life and health. It is crucial to thoroughly investigate the mechanisms of esophageal carcinogenesis and identify potential key molecular events in its carcinogenesis. Single‐cell transcriptome sequencing is an emerging technology that has gained prominence in recent years for studying molecular mechanisms, which may help to further explore the underlying mechanisms of the ESCC tumor microenvironment in depth. The single‐cell dataset was obtained from GSE160269 in the Gene Expression Omnibus database, including 60 tumor samples and four paracancer samples. The single‐cell data underwent dimensional reduction clustering analysis to identify clusters and annotate expression profiles. Subcluster analysis was conducted for each cellular taxon. Copy number variation analysis of tumor cell subpopulations was performed to primarily identify malignant cells within them. A proposed chronological analysis was performed to obtain the process of cell differentiation. In addition, cell communication, transcription factor analysis, and tumor pathway analysis were also performed. Relevant risk models and key genes were established by univariate COX regression and LASSO analysis. The key genes obtained from the screen were subjected to appropriate silencing and cellular assays, including CCK‐8, 5‐ethynyl‐2′‐deoxyuridine, colony formation, and western blot. Single‐cell analysis revealed that normal samples contained a large number of fibroblasts, T cells, and B cells, with fewer other cell types, whereas tumor samples exhibited a relatively balanced distribution of cell types. Subclassification analysis of immune cells, fibroblasts, endothelial cells, and epithelial cells revealed their specific spatial characteristics. The prognostic risk model, we constructed successfully, achieved accurate prognostic stratification for ESCC patients. The screened key gene, UPF3A, was found to be significantly associated with the development of ESCC by cellular assays. This process might be linked to the phosphorylation of ERK and P38. Single‐cell transcriptome analysis successfully revealed the distribution of cell types and major expressed factors in ESCC patients, which could facilitate future in‐depth studies on the therapeutic mechanisms of ESCC.
Globular adiponectin induces esophageal adenocarcinoma cell pyroptosis via the miR‐378a‐3p/UHRF1 axis
Authors: Wang Jun , Cheng Yan , Xiaoran Yin , Chen Fengrong , Jie Wu , Yahui Huang , Yue Wang , Dong Liu , Yumei Luo , Cheng Feng , Libo Zhang , Jun Zhang
Published: April 2024

Background

Antiapoptosis is a major factor in the resistance of tumor cells to chemotherapy and radiotherapy. Thus, activation of cell pyroptosis may be an effective option to deal with antiapoptotic cancers such as esophageal adenocarcinoma (EAC).

Methods

Differential expression of ubiquitin‐like versus PHD and ring finger structural domain 1 (UHRF1) in EAC and near normal tissues was analyzed, as well as the prognostic impact on survival in EAC. Also, the same study was done for globular adiponectin (gAD). Simultaneously, the mRNA expression of UHRF1 was observed in different EAC cell lines. Real time cellular analysis (RTCA) was used to detect cell proliferation, and flow cytometry and inverted fluorescence microscopy were used to detect pyroptosis. Biocredit analysis was conducted to observe the correlation between UHRF1 and key pyroptosis proteins. OD values and CCK8 assay were used to determine the effect of miR‐378a‐3p on EAC cells. Quantitative real‐time polymerase chain reaction and Western blot were used to detect the correlation between UHRF1, gAD, and miR‐378a‐3p in EAC cells. Moreover, in vivo and in vitro experiments were performed to detect the relevant effects on tumor migration and invasion after inhibiting UHRF1 expression.

Results

UHRF1 was negatively correlated with the survival of patients with EAC, while miR‐378a‐3p showed the opposite effect. Additionally, gAD promoted EAC cell pyroptosis, upregulated miR‐378a‐3p, and significantly inhibited the proliferation of EAC cells. gAD directly reduced UHRF1 expression in EAC cells by upregulating miR‐378a‐3p. In cell migration and invasion assays, inhibition of UHRF1 expression significantly suppressed EAC cell metastasis. In animal experiments, we again demonstrated that gAD induced pyroptosis in EAC cells by inhibiting the expression of UHRF1.

Conclusion

gAD‐induced upregulation of miR‐378a‐3p significantly inhibited the proliferation of EAC by targeting UHRF1. Therefore, gAD may serve as an alternative therapy for chemotherapy‐ and radiation‐refractory EAC or other cancers with the same mechanism of pyroptosis action.
Torque‐tuned I‐V characteristics in a piezoelectric semiconductor composite fiber
Authors: Zhang Gongye , Mei Yanjie , Mi Changwen , Qu Yilin
Published: April 2024

This paper studies the multi‐physical fields in a torsional composite fiber composed of a non‐piezoelectric semiconductor (PS) core coated with a piezoelectric dielectric shell. Based on the three‐dimensional framework of piezoelectricity and drift‐diffusion theory, we develop a nonlinear one‐dimensional model that incorporates the warping deformation, shear deformation, and axial variations of the electric field and charge transportations. A One‐dimensional model is linearized for small perturbations of charges, and we obtain the analytical solutions for single rods or PN junctions when torques are applied, which explicitly illustrates the electromechanical fields and redistribution of mobile charges. We also examine how the thickness of the composite rods affects the interaction between the piezoelectric and semiconductor components in the model. The optimal thickness ratio for maximizing the overall mobility of carriers has been discovered. This enables us to modify the thickness ratio to achieve the greatest PS interaction performance. Based on the nonlinear equations, we analyze the relationships between electric currents and applied voltages on the end of rods. Finally, we examine how twisting moments influence the characteristics of this I‐V relationship. The presented study provides a potential application for mechanical switches or sensors for PSs.
Determinization of Integral Discounted-Sum Automata is Decidable
Authors: Almagor Shaull , Dafni Neta
Published: April 2024

Nondeterministic Discounted-Sum Automata (NDAs) are nondeterministic finite automata equipped with a discounting factor $$\lambda >1$$

λ
>
1

, and whose transitions are labelled by weights. The value of a run of an NDA is the discounted sum of the edge weights, where the i-th weight is divided by $$\lambda ^{i}$$

λ
i

. NDAs are a useful tool for modelling systems where the values of future events are less influential than immediate ones.

While several problems are undecidable or open for NDA, their deterministic fragment (DDA) admits more tractable algorithms. Therefore, determinization of NDAs (i.e., deciding if an NDA has a functionally-equivalent DDA) is desirable.

Previous works establish that when $$\lambda \in \mathbb {N}$$

λ
∈
N

, then every complete NDA, namely an NDA whose states are all accepting and its transition function is complete, is determinizable. This, however, no longer holds when the completeness assumption is dropped.

We show that the problem of whether an NDA has an equivalent DDA is decidable when $$\lambda \in \mathbb {N}$$

λ
∈
N

(in particular, it is in $$\textsf{EXPSPACE}$$
EXPSPACE
and is $$\mathsf {PSPACE-hard}$$

PSPACE
-
hard

).
Checking History-Determinism is NP-hard for Parity Automata
Authors: Prakash Aditya
Published: April 2024

We show that the problem of checking if a given nondeterministic parity automaton simulates another given nondeterministic parity automaton is NP-hard. We then adapt the techniques used for this result to show that the problem of checking history-determinism for a given parity automaton is NP-hard. This is an improvement from Kuperberg and Skrzypczak’s previous lower bound of solving parity games from 2015. We also show that deciding if Eve wins the one-token game or the two-token game of a given parity automaton is NP-hard. Finally, we show that the problem of deciding if the language of a nondeterministic parity automaton is contained in the language of a history-deterministic parity automaton can be solved in quasi-polynomial time.
Monoidal Extended Stone Duality
Authors: Birkmann Fabian , Urbat Henning , Milius Stefan
Published: April 2024

Extensions of Stone-type dualities have a long history in algebraic logic and have also been instrumental for proving results in algebraic language theory. We show how to extend abstract categorical dualities via monoidal adjunctions, subsuming various incarnations of classical extended Stone and Priestley duality as a special case. Guided by these categorical foundations, we investigate residuation algebras, which are algebraic models of language derivatives, and show the subcategory of derivation algebras to be dually equivalent to the category of profinite ordered monoids, restricting to a duality between boolean residuation algebras and profinite monoids. We further extend this duality to capture relational morphisms of profinite ordered monoids, which dualize to natural morphisms of residuation algebras.
Towards a Compositional Framework for Convex Analysis (with Applications to Probability Theory)
Authors: Stein Dario , Samuelson Richard
Published: April 2024

We introduce a compositional framework for convex analysis based on the notion ofconvex bifunctionof Rockafellar. This framework is well-suited to graphical reasoning, and exhibits rich dualities such as the Legendre-Fenchel transform, while generalizing formalisms like graphical linear algebra, convex relations and convex programming. We connect our framework to probability theory by interpreting the Laplace approximation in its context: The exactness of this approximation on normal distributions means that logdensity is a functor from Gaussian probability (densities and integration) to concave bifunctions and maximization.
CTMCs with Imprecisely Timed Observations
Authors: Badings Thom , Volk Matthias , Junges Sebastian , Stoelinga Marielle , Jansen Nils
Published: April 2024

Labeled continuous-time Markov chains (CTMCs) describe processes subject to random timing and partial observability. In applications such as runtime monitoring, we must incorporate past observations. The timing of these observations matters but may be uncertain. Thus, we consider a setting in which we are given a sequence of imprecisely timed labels called the evidence. The problem is to compute reachability probabilities, which we condition on this evidence. Our key contribution is a method that solves this problem by unfolding the CTMC states over all possible timings for the evidence. We formalize this unfolding as a Markov decision process (MDP) in which each timing for the evidence is reflected by a scheduler. This MDP has infinitely many states and actions in general, making a direct analysis infeasible. Thus, we abstract the continuous MDP into a finite interval MDP (iMDP) and develop an iterative refinement scheme to upper-bound conditional probabilities in the CTMC. We show the feasibility of our method on several numerical benchmarks and discuss key challenges to further enhance the performance.
Dissipative quadratizations of polynomial ODE systems
Authors: Cai Yubo , Pogudin Gleb
Published: April 2024

Quadratization refers to a transformation of an arbitrary system of polynomial ordinary differential equations to a system with at most quadratic right-hand side. Such a transformation unveils new variables and model structures that facilitate model analysis, simulation, and control and offer a convenient parameterization for data-driven approaches. Quadratization techniques have found applications in diverse fields, including systems theory, fluid mechanics, chemical reaction modeling, and mathematical analysis.

In this study, we focus on quadratizations that preserve the stability properties of the original model, specifically dissipativity at given equilibria. This preservation is desirable in many applications of quadratization including reachability analysis and synthetic biology. We establish the existence of dissipativity-preserving quadratizations, develop an algorithm for their computation, and demonstrate it in several case studies.
Towards Safe Autonomous Driving: Model Checking a Behavior Planner during Development
Authors: König Lukas , Heinzemann Christian , Griggio Alberto , Klauck Michaela , Cimatti Alessandro , Henze Franziska , Tonetta Stefano , Küperkoch Stefan , Fassbender Dennis , Hanselmann Michael
Published: April 2024

Automated driving functions are among the most critical software components to develop. Before deployment in series vehicles, it has to be shown that the functions drive safely and in compliance with traffic rules. Despite the coverage that can be reached with very large amounts of test drives, corner cases remain possible. Furthermore, the development is subject to time-to-delivery constraints due to the highly competitive market, and potential logical errors must be found as early as possible. We describe an approach to improve the development of an actual industrial behavior planner for the Automated Driving Alliance between Bosch and Cariad. The original process landscape for verification and validation is extended with model checking techniques. The idea is to integrate automated extraction mechanisms that, starting from the C++ code of the planner, generate a higher-level model of the underlying logic. This model, composed in closed loop with expressive environment descriptions, can be exhaustively analyzed with model checking. This results, in case of violations, in traces that can be re-executed in system simulators to guide the search for errors. The approach was exemplarily deployed in series development, and successfully found relevant issues in intermediate versions of the planner at development time.
Mata: A Fast and Simple Finite Automata Library
Authors: Chocholatý David , Fiedor Tomáš , Havlena Vojtěch , Holík Lukáš , Hruška Martin , Lengál Ondřej , Síč Juraj
Published: April 2024

Mata is a well-engineered automata library written in C++ that offers a unique combination of speed and simplicity. It is meant to serve in applications such as string constraint solving and reasoning about regular expressions, and as a reference implementation of automata algorithms. Besides basic algorithms for (non)deterministic automata, it implements a fast simulation reduction and antichain-based language inclusion checking. The simplicity allows a straightforward access to the low-level structures, making it relatively easy to extend and modify. Besides the C++ API, the library also implements a Python binding.

The library comes with a large benchmark of automata problems collected from relevant applications such as string constraint solving, regular model checking, and reasoning about regular expressions. We show that Mata is on this benchmark significantly faster than all libraries from a wide range of automata libraries we collected. Its usefulness in string constraint solving is demonstrated by the string solver Z3-Noodler, which is based on Mata and outperforms the state of the art in string constraint solving on many standard benchmarks.
Rabin Games and Colourful Universal Trees
Authors: Majumdar Rupak , Sağlam Irmak , Thejaswini K. S.
Published: April 2024

We provide an algorithm to solve Rabin and Streett games over graphs with n vertices, m edges, and k colours that runs in $$\tilde{O}\left( mn(k!)^{1+o(1)} \right) $$

O
~

m
n

(
k
!
)

1
+
o
(
1
)

time and $$O(nk\log k \log n)$$

O
(
n
k
log
k
log
n
)

space, where $$\tilde{O}$$

O
~

hides poly-logarithmic factors. Our algorithm is an improvement by a super quadratic dependence on k! from the currently best known run time of $$O\left( mn^2(k!)^{2+o(1)}\right) $$

O

m

n
2

(
k
!
)

2
+
o
(
1
)

, obtained by converting a Rabin game into a parity game, while simultaneously improving its exponential space requirement.

Our main technical ingredient is a characterisation of progress measures for Rabin games using colourful trees and a combinatorial construction of succinctly-represented, universal colourful trees. Colourful universal trees are generalisations of universal trees used by Jurdziński and Lazić (2017) to solve parity games, as well as of Rabin progress measures of Klarlund and Kozen (1991). Our algorithm for Rabin games is a progress measure lifting algorithm where the lifting is performed on succinct, colourful, universal trees.
Verification under TSO with an infinite Data Domain
Authors: Abdulla Parosh Aziz , Atig Mohamed Faouzi , Furbach Florian , Garg Shashwat
Published: April 2024

We examine verification of concurrent programs under the total store ordering (TSO) semantics used by thex86architecture. In our model, threads manipulate variables over infinite domains and they can check whether variables are related for a range of relations. We show that, in general, the control state reachability problem is undecidable. This result is derived through a reduction from the state reachability problem of lossy channel systems with data (which is known to be undecidable).

In the light of this undecidability, we turn our attention to a more tractable variant of the reachability problem. Specifically, we study context bounded runs, which provide an under-approximation of the program behavior by limiting the possible interactions between processes. A run consists of a number of contexts, with each context representing a sequence of steps where a only single designated thread is active. We prove that the control state reachability problem under bounded context switching is PSPACE complete.
ConcurrentWitness2Test: Test-Harnessing the Power of Concurrency (Competition Contribution)
Authors: Bajczi Levente , Ádám Zsófia , Micskei Zoltán
Published: April 2024

ConcurrentWitness2Testis a violation witness validator for concurrent software. Taking both nondeterminism of data and interleaving-based nondeterminism into account, the tool aims to use the metadata described in the violation witnesses to synthesize an executable test harness. While plagued by some initial challenges yet to overcome, the validation performance ofConcurrentWitness2Testcorroborates the usefulness of the proposed approach.
Goblint Validator: Correctness Witness Validation by Abstract Interpretation
Authors: Saan Simmo , Erhard Julian , Schwarz Michael , Bozhilov Stanimir , Holter Karoliine , Tilscher Sarah , Vojdani Vesal , Seidl Helmut
Published: April 2024

Goblintis an abstract interpretation framework for C programs with a specialty in concurrency. Using a novel approach, we turn it into a validator of YAML correctness witnesses for all SV-COMP categories. We describe its results at SV-COMP 2024 which includes the first large-scale evaluation of our validator.
AISE: A Symbolic Verifier by Synergizing Abstract Interpretation and Symbolic Execution (Competition Contribution)
Authors: Wang Zhen , Chen Zhenbang
Published: April 2024

is a static verifier that can verify the safety properties of C programs. The core of is a program verification framework that synergizes abstract interpretation and symbolic execution in a novel manner. Compared to the individual application of symbolic execution or abstract interpretation, has better efficiency and precision. The implementation of is based on and .
CPV: A Circuit-Based Program Verifier
Authors: Chien Po-Chun , Lee Nian-Ze
Published: April 2024

We submit to SV-COMP 2024CPV, a circuit-based software verifier for C programs.CPVutilizes sequential circuits as its intermediate representation and invokes hardware model checkers to analyze the reachability safety of C programs. As the frontend, it usesKratos2, a recently proposed verification tool, to translate a C program to a sequential circuit. As the backend, state-of-the-art hardware model checkersABCandAVRare employed to verify the translated circuits. We configure the hardware model checkers to run various analyses, including IC3/PDR, interpolation-based model checking, and$$k$$k-induction. Information discovered by hardware model checkers is represented as verification witnesses. In the competition,CPVachieved comparable performance against participants whose intermediate representations are based on control-flow graphs. In the categoryReachSafety, it outperformed several mature software verifiers as a first-year participant.CPVmanifests the feasibility of sequential circuits as an alternative intermediate representation for program analysis and enables head-to-head algorithmic comparison between hardware and software verification.
PROTON: PRObes for Termination Or Not (Competition Contribution)
Authors: Metta Ravindra , Karmarkar Hrishikesh , Madhukar Kumar , Venkatesh R. , Chakraborty Supratik
Published: April 2024

PROTON is a tool to check whether a given C program has a non-terminating behaviour or not. It is built around the C Bounded Model Checker (CBMC). CBMC cannot prove non-termination directly, as all non-terminating runs are unbounded. PROTON annotates the loops in a given program with assertions that check for a recurrent program state. Violation of such an assertion shows the existence of a recurrent state and thereby proves non-termination. PROTON also transforms the violating trace returned by CBMC into a non-termination witness for the program.
Gray-Box Fuzzing via Gradient Descent and Boolean Expression Coverage
Authors: Jonáš Martin , Strejček Jan , Trtík Marek , Urban Lukáš
Published: April 2024

We present a gray-box fuzzing approach based on several new ideas. While standard gray-box fuzzing aims to cover all branches of the input program, our approach primarily aims to cover both results of each Boolean expression. To achieve this goal, we track the distances to flipping these results and we dynamically detect the input bytes that influence the distance. Then we use this information to efficiently flip the results. More precisely, we apply gradient descent on the detected bytes or we create new inputs by using detected bytes from different inputs.

We implemented our approach in a tool called Fizzer. An evaluation on the benchmarks of Test-Comp 2023 shows that Fizzer is fully competitive with the winning tools of the competition, which use advanced formal methods like symbolic execution or bounded model checking, usually in combination with fuzzing.
Fast Symbolic Computation of Bottom SCCs
Authors: Jakobsen Anna Blume , Jørgensen Rasmus Skibdahl Melanchton , van de Pol Jaco , Pavlogiannis Andreas
Published: April 2024

The computation of bottom strongly connected components (BSCCs) is a fundamental task in model checking, as well as in characterizing the attractors of dynamical systems. As such, symbolic algorithms for BSCCs have received special attention, and are based on the idea that the computation of an SCC can be stopped early, as soon as it is deemed to be non-bottom.

In this paper we introduce $$\textsc {Pendant}$$

P

E
N
D
A
N
T

, a new symbolic algorithm for computing BSCCs which runs in linear symbolic time. In contrast to the standard approach of escaping non-bottom SCCs, $$\textsc {Pendant}$$

P

E
N
D
A
N
T

aims to start the computation from nodes that are likely to belong to BSCCs, and thus is more effective in sidestepping SCCs that are non-bottom. Moreover, we employ a simple yet powerful deadlock-detection technique, that quickly identifies singleton BSCCs before the main algorithm is run. Our experimental evaluation on three diverse datasets of 553 models demonstrates the efficacy of our two methods: $$\textsc {Pendant}$$

P

E
N
D
A
N
T

is decisively faster than the standard existing algorithm for BSCC computation, while deadlock detection improves the performance of each algorithm significantly.
Btor2-Cert: A Certifying Hardware-Verification Framework Using Software Analyzers
Authors: Ádám Zsófia , Beyer Dirk , Chien Po-Chun , Lee Nian-Ze , Sirrenberg Nils
Published: April 2024

Formal verification is essential but challenging: Even the best verifiers may produce wrong verification verdicts.Certifyingverifiers enhance the confidence in verification results by generating awitnessfor other tools to validate the verdict independently. Recently, translating the hardware-modeling languageBtor2to software, such as the programming language C or LLVM intermediate representation, has been actively studied and facilitated verifying hardware designs by software analyzers. However, it remained unknown whether witnesses produced by software verifiers contain helpful information about the original circuits and how such information can aid hardware analysis. We propose a certifying and validating frameworkBtor2-Certto verify safety properties ofBtor2circuits, combiningBtor2-to-C translation, software verifiers, and a new witness validatorBtor2-Val, to answer the above open questions.Btor2-Certtranslates a softwareviolation witnessto aBtor2violation witness; As theBtor2language lacks a format forcorrectness witnesses, we encode invariants in software correctness witnesses asBtor2circuits. The validatorBtor2-Valchecks violation witnesses by circuit simulation and correctness witnesses byvalidation via verification. In our evaluation,Btor2-Certsuccessfully utilized software witnesses to improve quality assurance of hardware. By invoking the software verifierCbmcon translated programs, it uniquely solved, with confirmed witnesses, 8 % of the unsafe tasks for which the hardware verifierABCfailed to detect bugs.
Auction-Based Scheduling
Authors: Avni Guy , Mallik Kaushik , Sadhukhan Suman
Published: April 2024

Sequential decision-making tasks often require satisfaction of multiple, partially-contradictory objectives. Existing approaches are monolithic, where a singlepolicyfulfills all objectives. We presentauction-based scheduling, adecentralizedframework for multi-objective sequential decision making. Each objective is fulfilled using a separate and independent policy. Composition of policies is performed at runtime, where at each step, the policies simultaneously bid from pre-allocated budgets for the privilege of choosing the next action. The framework allows policies to be independently created, modified, and replaced. We study path planning problems on finite graphs with two temporal objectives and present algorithms to synthesize policies together with bidding policies in a decentralized manner. We consider three categories of decentralized synthesis problems, parameterized by the assumptions that the policies make on each other. We identify a class of assumptions calledassume-admissiblefor which synthesis is always possible for graphs whose every vertex has at most two outgoing edges.
Definitional Functoriality for Dependent (Sub)Types
Authors: Laurent Théo , Lennon-Bertrand Meven , Maillard Kenji
Published: April 2024

Dependently typed proof assistant rely crucially on definitional equality, which relates types and terms that are automatically identified in the underlying type theory. This paper extends type theory with definitional functor laws, equations satisfied propositionally by a large class of container-like type constructors $$F : {\text {Type}}\rightarrow {\text {Type}}$$

F
:
Type
→
Type

, equipped with a $$\textrm{map}_{F} {{\,\mathrm{:}\,}}(A \rightarrow B) \rightarrow F\,A \rightarrow F\,B$$

map
F

:

(
A
→
B
)

→
F

A
→
F

B

, such as lists or trees. Promoting these equations to definitional ones strengthens the theory, enabling slicker proofs and more automation for functorial type constructors. This extension is used to modularly justify a structural form of coercive subtyping, propagating subtyping through type formers in a map-like fashion. We show that the resulting notion of coercive subtyping, thanks to the extra definitional equations, is equivalent to a natural and implicit form of subsumptive subtyping. The key result of decidability of type-checking in a dependent type system with functor laws for lists has been entirely mechanized in Coq.
Layered Modal Type Theory
Authors: Hu Jason Z. S. , Pientka Brigitte
Published: April 2024

We introduce layering to modal type theory to combine type theory with intensional analysis. In particular, we demonstrate this idea by developing a 2-layered modal type theory. At the core of this type theory (layer 0) is a simply typed $$\lambda $$
λ
-calculus with no modality. Layer 1 is obtained by extending the core language with one layer of contextual $$\square $$
□
types to support pattern matching on potentially open code from layer 0 while retaining normalization. Although both layers fundamentally share the same language and the same typing judgment, we only allow computation at layer 1. As a consequence, layer 0 accurately captures the syntactic representation of code in contrast to the computational behaviors at layer 1. The system is justified by normalization by evaluation (NbE) using a presheaf model. The normalization algorithm extracted from the model is sound and complete and is implemented in Agda.

Layered modal type theory provides a uniform foundation for meta-programming with intensional analysis. We see this work as an important step towards a foundational way to support meta-programming in proof assistants.
Program Synthesis from Graded Types
Authors: Hughes Jack , Orchard Dominic
Published: April 2024

Graded type systems are a class of type system for fine-grained quantitative reasoning about data-flow in programs. Through the use of resource annotations (or grades), a programmer can express various program properties at the type level, reducing the number of typeable programs. These additional constraints on types lend themselves naturally to type-directed program synthesis, where this information can be exploited to constrain the search space of programs. We present a synthesis algorithm for a graded type system, where grades form an arbitrary pre-ordered semiring. Harnessing this grade information in synthesis is non-trivial, and we explore some of the issues involved in designing and implementing a resource-aware program synthesis tool. In our evaluation we show that by harnessing grades in synthesis, the majority of our benchmark programs (many of which involve recursive functions over recursive ADTs) require less exploration of the synthesis search space than a purely type-driven approach and with fewer needed input-output examples. This type-and-graded-directed approach is demonstrated for the research language Granule but we also adapt it for synthesising Haskell programs that use GHC’s linear types extension.
A Formal Treatment of Bidirectional Typing
Authors: Chen Liang-Ting , Ko Hsiang-Shang
Published: April 2024

There has been much progress in designing bidirectional type systems and associated type synthesis algorithms, but mainly on a case-by-case basis. To remedy the situation, this paper develops a general and formal theory of bidirectional typing for simply typed languages: for every signature that specifies a mode-correct bidirectionally typed language, there exists a proof-relevant type synthesiser which, given an input abstract syntax tree, constructs a typing derivation if any, gives its refutation if not, or reports that the input does not have enough type annotations. Sufficient conditions for deriving a type synthesiser such as soundness, completeness, and mode-correctness are studied universally for all signatures. We propose a preprocessing step called mode decoration, which helps the user to deal with missing type annotations. The entire theory is formally implemented in Agda, so we provide a verified generator of proof-relevant type synthesisers as a by-product of our formalism.
Generic bidirectional typing for dependent type theories
Authors: Felicissimo Thiago
Published: April 2024

Bidirectional typing is a discipline in which the typing judgment is decomposed explicitly into inference and checking modes, allowing to control the flow of type information in typing rules and to specify algorithmically how they should be used. Bidirectional typing has been fruitfully studied and bidirectional systems have been developed for many type theories. However, the formal development of bidirectional typing has until now been kept confined to specific theories, with general guidelines remaining informal. In this work, we give a generic account of bidirectional typing for a general class of dependent type theories. This is done by first giving a general definition of type theories (or equivalently, a logical framework), for which we define declarative and bidirectional type systems. We then show, in a theory-independent fashion, that the two systems are equivalent. This equivalence is then explored to establish the decidability of typing for weak normalizing theories, yielding a generic type-checking algorithm that has been implemented in a prototype and used in practice with many theories.
A Modular Soundness Theory for the Blackboard Analysis Architecture
Authors: Keidel Sven , Helm Dominik , Roth Tobias , Mezini Mira
Published: April 2024

Sound static analyses are an important ingredient for compiler optimizations and program verification tools. However, mathematically proving that a static analysis is sound is a difficult task due to two problems. First, soundness proofs relate two complicated program semantics (the static and the dynamic semantics) which are hard to reason about. Second, the more the static and dynamic semantics differ, the more work a soundness proof needs to do to bridge the impedance mismatch. These problems increase the effort and complexity of soundness proofs. Existing soundness theories address these problems by deriving both the dynamic and static semantics from the same artifact, often called generic interpreter. A generic interpreter provides a common structure along which a soundness proof can be composed, which avoids having to reason about the analysis as a whole. However, a generic interpreter restricts which analyses can be derived, as all derived analyses must roughly follow the program execution order.

To lift this restriction, we develop a soundness theory for the blackboard analysis architecture, which is capable of describing backward, demand-driven, and summary-based analyses. The architecture describes static analyses with small independent modules, which communicate via a central store. Soundness of a compound analysis follows from soundness of all of its modules. Furthermore, modules can be proven sound independently, even though modules depend on each other. We evaluate our theory by proving soundness of four analyses: a pointer and call-graph analysis, a reflection analysis, an immutability analysis, and a demand-driven reaching definitions analysis.
Detection of Uncaught Exceptions in Functional Programs by Abstract Interpretation
Authors: Lermusiaux Pierre , Montagu Benoît
Published: April 2024

Exception handling is a key feature in modern programming languages. Exceptions can be used to deal with errors, or as a means to control the flow of execution of a program. Since they might unexpectedly terminate a program, unhandled exceptions are a serious safety concern. We propose a static analysis to detect uncaught exceptions in functional programs, that is defined as an abstract interpreter. It computes a description of the values potentially returned by a program using a novel abstract domain, that can express inductively defined sets of values. Simultaneously, the analysis infers the possibly raised exceptions, by computing in theabstract exception monad. This abstract interpreter has been implemented as an effective static analyser for a large subset of programs, that supports mutable data types, the module system, and dynamically extensible data types such as the exception type. The analyser has been evaluated on several hundreds of programs.