Search

We present a new angle on solving quantified linear integer arithmetic based on combining the automata-based approach, where numbers are understood as bitvectors, with ideas from (nowadays prevalent) algebraic approaches, which work directly with numbers. This combination is enabled by a fine-grained version of the duality between automata and arithmetic formulae. In particular, we employ a construction where states of automaton are obtained as derivatives of arithmetic formulae: then every state corresponds to a formula. Optimizations based on techniques and ideas transferred from the world of algebraic methods are used on thousands of automata states, which dramatically amplifies their effect. The merit of this combination of automata with algebraic methods is demonstrated by our prototype implementation being competitive to and even superior to state-of-the-art SMT solvers., Comment: Accepted to CAV'24

We propose a data-driven algorithm for numerical invariant synthesis and verification. The algorithm is based on the ICE-DT schema for learning decision trees from samples of positive and negative states and implications corresponding to program transitions. The main issue we address is the discovery of relevant attributes to be used in the learning process of numerical invariants. We define a method for solving this problem guided by the data sample. It is based on the construction of a separator that covers positive states and excludes negative ones, consistent with the implications. The separator is constructed using an abstract domain representation of convex sets. The generalization mechanism of the decision tree learning from the constraints of the separator allows the inference of general invariants, accurate enough for proving the targeted property. We implemented our algorithm and showed its efficiency.

We consider a first-order logic for the integers with addition. This logic extends classical first-order logic by modulo-counting, threshold-counting and exact-counting quantifiers, all applied to tuples of variables (here, residues are given as terms while moduli and thresholds are given explicitly). Our main result shows that satisfaction for this logic is decidable in two-fold exponential space. If only threshold- and exact-counting quantifiers are allowed, we prove an upper bound of alternating two-fold exponential time with linearly many alternations. This latter result almost matches Berman's exact complexity of first-order logic without counting quantifiers. To obtain these results, we first translate threshold- and exact-counting quantifiers into classical first-order logic in polynomial time (which already proves the second result). To handle the remaining modulo-counting quantifiers for tuples, we first reduce them in doubly exponential time to modulo-counting quantifiers for single elements. For these quantifiers, we provide a quantifier elimination procedure similar to Reddy and Loveland's procedure for first-order logic and analyse the growth of coefficients, constants, and moduli appearing in this process. The bounds obtained this way allow to restrict quantification in the original formula to integers of bounded size which then implies the first result mentioned above. Our logic is incomparable with the logic considered by Chistikov et al. in 2022. They allow more general counting operations in quantifiers, but only unary quantifiers. The move from unary to non-unary quantifiers is non-trivial, since, e.g., the non-unary version of the H\"artig quantifier results in an undecidable theory.

In this study, the sensitivity of future lepton colliders to WIMP dark matter is evaluated assuming WIMP pair production accompanied by a photon from initial state radiation, through which the process can be identified. A full detector simulation for the International Large Detector (ILD) concept at the International Linear Collider (ILC) is performed for a \com energy of 500\,GeV. Energy scales of up to $3$\,TeV can be tested for different effective operators for WIMP masses almost up to half the \com energy. The sensitivity benefits from the polarised beams, which can reduce the main SM background from neutrino pair production substantially. In addition, systematic uncertainties are shown to be significantly reduced by combining data with several different polarisation configurations. In comparison to a previous study, the reconstruction of the forward detectors has been improved and the systematic uncertainties are fully treated. The results are also extrapolated to other \com energies, luminosities and beam polarisations. This allows to provide results for the full ILC programme, i.e.\ from 250\,GeV to 1\,TeV, as well as to give approximate results for other planned lepton colliders., Comment: 30 pages, 21 figures

This paper investigates the connexion between the Kannan-Lipton Orbit Problem and the polynomial invariant generator algorithm PILA based on eigenvectors computation. Namely, we reduce the problem of generating linear and polynomial certificates of non-reachability for the Orbit Problem for linear transformations with rational coefficients to the generalized eigenvector problem. Also, we prove the existence of such certificates for any transformation with integer coefficients, which is not the case with rational coefficients., Comment: 12 pages + references, submutted to ICALP 2018

The International Linear Collider is now proposed with a staged machine design, with the first stage at $\sqrt{s}=$~250 GeV and an integrated luminosity goal of 2~ab$^{-1}$. One of the questions for the machine design is the importance of positron polarization. In this report, we review the impact of positron polarization on the physics goals of the $250$ GeV stage of the ILC and demonstrate that positron polarization has distinct advantages., Comment: 19

The International Linear Collider is now proposed with a staged machine design, with the first stage at 250 GeV with a luminosity goal of 2 ab-1. In this paper, we review the physics expectations for this machine. These include precision measurements of Higgs boson couplings, searches for exotic Higgs decays, other searches for particles that decay with zero or small visible energy, and measurements of e+e- annihilation to W+W- and 2-fermion states with improved sensitivity. A summary table gives projections for the achievable levels of precision based on the latest full simulation studies., Comment: 48 pages, 6 tables, 12 figures; v3: Figures 1, 2, 5 replaced by corrected versions; v4: typo in eq. (16) corrected

We study several extensions of linear-time and computation-tree temporal logics with quantifiers that allow for counting how often certain properties hold. For most of these extensions, the model-checking problem is undecidable, but we show that decidability can be recovered by considering flat Kripke structures where each state belongs to at most one simple loop. Most decision procedures are based on results on (flat) counter systems where counters are used to implement the evaluation of counting operators., Comment: Extended version providing an additional appendix

Weakly Interacting Massive Particles (WIMPs, $\chi$) are candidates for Dark Matter. WIMP searches at lepton colliders are complementary to searches at hadron colliders and direct and indirect detection, since they directly probe the coupling to electrons which a priori is independent of the coupling to hadrons. Like at hadron colliders, WIMP pair production can be observed via an additional tag particle, in particular a photon from initial state radiation ($e^+e^-\rightarrow\chi\chi\gamma$). With this technique WIMP masses to nearly half the centre-of-mass energy can be probed. Polarised beams are essential to reduce Standard Model backgrounds and to characterize the properties of the new particles in case a signal is discovered. Prospects for a mono-photon WIMP study at the International Linear Collider will be discussed in the context of EFT. In addition, detector requirements will be presented.

Automated writing evaluation (AWE) has been shown to be an effective mechanism for quickly providing feedback to students. It has already seen wide adoption in enterprise-scale applications and is starting to be adopted in large-scale contexts. Training an AWE model has historically required a single batch of several hundred writing examples and human scores for each of them. This requirement limits large-scale adoption of AWE since human-scoring essays is costly. Here we evaluate algorithms for ensuring that AWE models are consistently trained using the most informative essays. Our results show how to minimize training set sizes while maximizing predictive performance, thereby reducing cost without unduly sacrificing accuracy. We conclude with a discussion of how to integrate this approach into large-scale AWE systems.

We introduce session automata, an automata model to process data words, i.e., words over an infinite alphabet. Session automata support the notion of fresh data values, which are well suited for modeling protocols in which sessions using fresh values are of major interest, like in security protocols or ad-hoc networks. Session automata have an expressiveness partly extending, partly reducing that of classical register automata. We show that, unlike register automata and their various extensions, session automata are robust: They (i) are closed under intersection, union, and (resource-sensitive) complementation, (ii) admit a symbolic regular representation, (iii) have a decidable inclusion problem (unlike register automata), and (iv) enjoy logical characterizations. Using these results, we establish a learning algorithm to infer session automata through membership and equivalence queries.

We consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution there may be many graphs representing it. However, one of these graphs is of path-width at most 2n, where n is the number of variables in the instance. Since FO is decidable on graphs of bounded path- width, we obtain an alternative decidability result for ILP. The technique we use underlines a common principle to prove decidability which has previously been employed for automata with auxiliary storage. We also show how this new result links to automata theory and program verification., Comment: In Proceedings GandALF 2014, arXiv:1408.5560

We study temporal logics and automata on multi-attributed data words. Recently, BD-LTL was introduced as a temporal logic on data words extending LTL by navigation along positions of single data values. As allowing for navigation wrt. tuples of data values renders the logic undecidable, we introduce ND-LTL, an extension of BD-LTL by a restricted form of tuple-navigation. While complete ND-LTL is still undecidable, the two natural fragments allowing for either future or past navigation along data values are shown to be Ackermann-hard, yet decidability is obtained by reduction to nested multi-counter systems. To this end, we introduce and study nested variants of data automata as an intermediate model simplifying the constructions. To complement these results we show that imposing the same restrictions on BD-LTL yields two 2ExpSpace-complete fragments while satisfiability for the full logic is known to be as hard as reachability in Petri nets.

We present results from our analysis of Chandra X-ray Observatory, W. M. Keck Observatory, and Karl G. Jansky Very Large Array (VLA) images of the Crab Nebula that were contemporaneous with the gamma-ray flare of 2011 April. Despite hints in the X-ray data, we find no evidence for statistically significant variations that pinpoint the specific location of the flares within the Nebula. The Keck observations extend this conclusion to the "inner knot", i.e., the feature within an arcsecond of the pulsar. The VLA observations support this conclusion. We also discuss theoretical implications of the gamma-ray flares and suggest that the most dramatic gamma-ray flares are due to radiation-reaction-limited synchrotron emission associated with sudden, dissipative changes in the current system sustained by the central pulsar., Comment: Accepted for publication by the Astrophysical Journal

We characterise the performance of a surface-electrode ion "chip" trap fabricated using established semiconductor integrated circuit and micro-electro-mechanical-system (MEMS) microfabrication processes which are in principle scalable to much larger ion trap arrays, as proposed for implementing ion trap quantum information processing. We measure rf ion micromotion parallel and perpendicular to the plane of the trap electrodes, and find that on-package capacitors reduce this to <~ 10 nm in amplitude. We also measure ion trapping lifetime, charging effects due to laser light incident on the trap electrodes, and the heating rate for a single trapped ion. The performance of this trap is found to be comparable with others of the same size scale., Comment: 6 pages, 10 figures