Search

In this paper we introduce the theory of derivatives of moments and (moment) functionals to represent moment functionals by Gaussian mixtures, characteristic functions of polytopes, and simple functions of polytopes. We study, among other measures, Gaussian mixtures, their reconstruction from moments and especially the number of Gaussians needed to represent moment functionals. We find that there are moment functionals $L:\mathbb{R}[x_1,\dots,x_n]_{\leq 2d}\to\mathbb{R}$ which can be represented by a sum of $\binom{n+2d}{n} - n\cdot \binom{n+d}{n} + \binom{n}{2}$ Gaussians but not less. Hence, for any $d\in\mathbb{N}$ and $\varepsilon>0$ we find an $n\in\mathbb{N}$ such that $L$ can be represented by a sum of $(1-\varepsilon)\cdot\binom{n+2d}{n}$ Gaussians but not less. An upper bound is $\binom{n+2d}{n}-1$., Comment: arXiv admin note: substantial text overlap with arXiv:1903.00598. Author note: This is part II of arXiv:1903.00598. arXiv:1903.00598 was extended and splitting it into two parts was necessary. Part I contains the Caratheodory number from Hilbert functions parts (now arXiv:1903.00598v2). Part II contains the (Gaussian) mixtures and shape reconstruction from derivatives of moments parts

We report on the fifth reactive synthesis competition (SYNTCOMP 2018). We introduce four new benchmark classes that have been added to the SYNTCOMP library, and briefly describe the evaluation scheme and the experimental setup of SYNTCOMP 2018. We give an overview of the participants of SYNTCOMP 2018 and highlight changes compared to previous years. Finally, we present and analyze the results of our experimental evaluation, including a ranking of tools with respect to quantity and quality of solutions., Comment: arXiv admin note: substantial text overlap with arXiv:1711.11439, arXiv:1609.00507

The synthesis of reactive systems from linear temporal logic (LTL) specifications is an important aspect in the design of reliable software and hardware. We present our adaption of the classic automata-theoretic approach to LTL synthesis, implemented in the tool Strix which has won the two last synthesis competitions (Syntcomp2018/2019). The presented approach is (1) structured, meaning that the states used in the construction have a semantic structure that is exploited in several ways, it performs a (2) forward exploration such that it often constructs only a small subset of the reachable states, and it is (3) incremental in the sense that it reuses results from previous inconclusive solution attempts. Further, we present and study different guiding heuristics that determine where to expand the on-demand constructed arena. Moreover, we show several techniques for extracting an implementation (Mealy machine or circuit) from the witness of the tree-automaton emptiness check. Lastly, the chosen constructions use a symbolic representation of the transition functions to reduce runtime and memory consumption. We evaluate the proposed techniques on the Syntcomp2019 benchmark set and show in more detail how the proposed techniques compare to the techniques implemented in other leading LTL synthesis tools.

A major hallmark of neural development is the oscillatory movement of nuclei between the apical and basal surfaces of the neuroepithelium during the process of interkinetic nuclear migration (IKNM). Here, we employ long-term, rapid lightsheet and two-photon imaging of zebrafish retinas $in~vivo$ during early development to uncover the physical processes that govern the behavior of nuclei during IKNM. These images allow the capture of reliable tracks of nuclear movements and division during early retinogenesis for many tightly packed nuclei. These tracks are then used to create and test a theory of retinal IKNM as a diffusive process across a nuclear concentration gradient generated by the addition of new nuclei at the apical surface. The analysis reveals the role of nuclear packing at the apical surface on the migration dynamics of nuclei, provides a robust quantitative explanation for the distribution of nuclei across the retina, and may have implications for stochastic fate choice in this system., Comment: 21 pages, 6 figures, data available on request

In this paper we improve the bounds for the Carath\'eodory number, especially on algebraic varieties and with small gaps (not all monomials are present). We provide explicit lower and upper bounds on algebraic varieties, $\mathbb{R}^n$, and $[0,1]^n$. We also treat moment problems with small gaps. We find that for every $\varepsilon>0$ and $d\in\mathbb{N}$ there is a $n\in\mathbb{N}$ such that we can construct a moment functional $L:\mathbb{R}[x_1,\dots,x_n]_{\leq d}\rightarrow\mathbb{R}$ which needs at least $(1-\varepsilon)\cdot\left(\begin{smallmatrix} n+d\\ n\end{smallmatrix}\right)$ atoms $l_{x_i}$. Consequences and results for the Hankel matrix and flat extension are gained. We find that there are moment functionals $L:\mathbb{R}[x_1,\dots,x_n]_{\leq 2d}\rightarrow\mathbb{R}$ which need to be extended to the worst case degree $4d$, $\tilde{L}:\mathbb{R}[x_1,\dots,x_n]_{\leq 4d}\rightarrow\mathbb{R}$, in order to have a flat extension., Comment: The first version contained the Carath\'eodory numbers from Hilbert functions and the shape reconstruction from derivatives of moments. The second part part extended and the paper is split into two papers: "Carath\'eodory numbers from Hilbert functions" and "Shape and Gaussian Mixture Reconstruction from Derivatives of Moments"

Free-Choice Workflow Petri nets, also known as Workflow Graphs, are a popular model in Business Process Modeling. In this paper we introduce Timed Probabilistic Workflow Nets (TPWNs), and give them a Markov Decision Process (MDP) semantics. Since the time needed to execute two parallel tasks is the maximum of the times, and not their sum, the expected time cannot be directly computed using the theory of MDPs with rewards. In our first contribution, we overcome this obstacle with the help of "earliest-first" schedulers, and give a single exponential-time algorithm for computing the expected time. In our second contribution, we show that computing the expected time is #P-hard, and so polynomial algorithms are very unlikely to exist. Further, #P-hardness holds even for workflows with a very simple structure in which all transitions times are 1 or 0, and all probabilities are 1 or 0.5. Our third and final contribution is an experimental investigation of the runtime of our algorithm on a set of industrial benchmarks. Despite the negative theoretical results, the results are very encouraging. In particular, the expected time of every workflow in a popular benchmark suite with 642 workflow nets can be computed in milliseconds.

Let $\mathsf{A}=\{a_1,\dots,a_m\}$, $m\in\mathbb{N}$, be measurable functions on a measurable space $(\mathcal{X},\mathfrak{A})$. If $\mu$ is a positive measure on $(\mathcal{X},\mathfrak{A})$ such that $\int a_i d\mu<\infty$ for all $i$, then the sequence $(\int a_1 d\mu,\dots,\int a_m d\mu)$ is called a moment sequence. By Richter's Theorem each moment sequence has a $k$-atomic representing measure with $k\leq m$. The set $\mathcal{S}_\mathsf{A}$ of all moment sequences is the moment cone. The aim of this paper is to analyze the various structures of the moment cone. The main results concern the facial structure (exposed faces, facial dimensions) and lower and upper bounds of the Carath\'eodory number (that is, the smallest number of atoms which suffices for all moment sequences) of the convex cone $\mathcal{S}_{\mathcal{A}}$. In the case when $\mathcal{X}\subseteq \mathbb{R}^n$ and $a_i\in C^1(\mathcal{X},\mathbb{R})$, the differential structure of the moment map and regularity/singularity properties of moment sequences are analyzed. The maximal mass problem is considered and some applications to other problems are sketched., Comment: 1 figure, 3 tables

We study truncated moment sequences of distribution mixtures, especially from Gaussian and log-normal distributions and their Carath\'eodory numbers. For $\mathsf{A} = \{a_1,\dots,a_m\}$ continuous (sufficiently differentiable) functions on $\mathbb{R}^n$ we give a general upper bound of $m-1$ and a general lower bound of $\left\lceil \frac{2m}{(n+1)(n+2)}\right\rceil$. For polynomials of degree at most $d$ in $n$ variables we find that the number of Gaussian and log-normal mixtures is bounded by the Carath\'eodory numbers in \cite{didio17Cara}. Therefore, for univariate polynomials $\{1,x,\dots,x^d\}$ at most $\left\lceil\frac{d+1}{2}\right\rceil$ distributions are needed. For bivariate polynomials of degree at most $2d-1$ we find that $\frac{3d(d-1)}{2}+1$ Gaussian distributions are sufficient. We also treat polynomial systems with gaps and find, e.g., that for $\{1,x^2,x^3,x^5,x^6\}$ 3 Gaussian distributions are enough for almost all truncated moment sequences. For log-normal distributions the number is bounded by half of the moment number. We give an example of continuous functions where more Gaussian distributions are needed than Dirac delta measures. We show that any inner truncated moment sequence has a mixture which contains any given distribution.

Workflow graphs extend classical flow charts with concurrent fork and join nodes. They constitute the core of business processing languages such as BPMN or UML Activity Diagrams. The activities of a workflow graph are executed by humans or machines, generically called resources. If concurrent activities cannot be executed in parallel by lack of resources, the time needed to execute the workflow increases. We study the problem of computing the minimal number of resources necessary to fully exploit the concurrency of a given workflow, and execute it as fast as possible (i.e., as fast as with unlimited resources). We model this problem using free-choice Petri nets, which are known to be equivalent to workflow graphs. We analyze the computational complexity of two versions of the problem: computing the resource and concurrency thresholds. We use the results to design an algorithm to approximate the concurrency threshold, and evaluate it on a benchmark suite of 642 industrial examples. We show that it performs very well in practice: It always provides the exact value, and never takes more than 30 milliseconds for any workflow, even for those with a huge number of reachable markings.

We present a flexible scheme to realize non-artificial non-Markovian dynamics of an electronic spin qubit, using a nitrogen-vacancy center in diamond where the inherent nitrogen spin serves as a regulator of the dynamics. By changing the population of the nitrogen spin, we show that we can smoothly tune the non-Markovianity of the electron spin's dynamic. Furthermore, we examine the decoherence dynamics induced by the spin bath to exclude other sources of non-Markovianity. The amount of collected measurement data is kept at a minimum by employing Bayesian data analysis. This allows for a precise quantification of the parameters involved in the description of the dynamics and a prediction of so far unobserved data points., Comment: 12 pages, 9 figure, including supplemental material

We consider the symbolic controller synthesis approach to enforce safety specifications on perturbed, nonlinear control systems. In general, in each state of the system several control values might be applicable to enforce the safety requirement and in the implementation one has the burden of picking a particular control value out of possibly many. We present a class of implementation strategies to obtain a controller with certain performance guarantees. This class includes two existing implementation strategies from the literature, based on discounted payoff and mean-payoff games. We unify both approaches by using games characterized by a single discount factor determining the implementation. We evaluate different implementations from our class experimentally on two case studies. We show that the choice of the discount factor has a significant influence on the average long-term costs, and the best performance guarantee for the symbolic model does not result in the best implementation. Comparing the optimal choice of the discount factor here with the previously proposed values, the costs differ by a factor of up to 50. Our approach therefore yields a method to choose systematically a good implementation for safety controllers with quantitative objectives.

We introduce a financial portfolio optimization framework that allows us to automatically select the relevant assets and estimate their weights by relying on a sorted $\ell_1$-Norm penalization, henceforth SLOPE. Our approach is able to group constituents with similar correlation properties, and with the same underlying risk factor exposures. We show that by varying the intensity of the penalty, SLOPE can span the entire set of optimal portfolios on the risk-diversification frontier, from minimum variance to the equally weighted. To solve the optimization problem, we develop a new efficient algorithm, based on the Alternating Direction Method of Multipliers. Our empirical analysis shows that SLOPE yields optimal portfolios with good out-of-sample risk and return performance properties, by reducing the overall turnover through more stable asset weight estimates. Moreover, using the automatic grouping property of SLOPE, new portfolio strategies, such as SLOPE-MV, can be developed to exploit the data-driven detected similarities across assets., Comment: 41 pages

Population protocols are a well established model of computation by anonymous, identical finite state agents. A protocol is well-specified if from every initial configuration, all fair executions reach a common consensus. The central verification question for population protocols is the well-specification problem: deciding if a given protocol is well-specified. Esparza et al. have recently shown that this problem is decidable, but with very high complexity: it is at least as hard as the Petri net reachability problem, which is EXPSPACE-hard, and for which only algorithms of non-primitive recursive complexity are currently known. In this paper we introduce the class WS3 of well-specified strongly-silent protocols and we prove that it is suitable for automatic verification. More precisely, we show that WS3 has the same computational power as general well-specified protocols, and captures standard protocols from the literature. Moreover, we show that the membership problem for WS3 reduces to solving boolean combinations of linear constraints over N. This allowed us to develop the first software able to automatically prove well-specification for all of the infinitely many possible inputs., Comment: 29 pages, 1 figure

This paper is about the moment problem on a finite-dimensional vector space of continuous functions. We investigate the structure of the convex cone of moment functionals (supporting hyperplanes, exposed faces, inner points) and treat various important special topics on moment functionals (determinacy, set of atoms of representing measures, core variety).

Let $\mathcal{A}$ be a finite-dimensional subspace of $C(\mathcal{X};\mathbb{R})$, where $\mathcal{X}$ is a locally compact Hausdorff space, and $\mathsf{A}=\{f_1,\dots,f_m\}$ a basis of $\mathcal{A}$. A sequence $s=(s_j)_{j=1}^m$ is called a moment sequence if $s_j=\int f_j(x) \, d\mu(x)$, $j=1,\dots,m$, for some positive Radon measure $\mu$ on $\mathcal{X}$. Each moment sequence $s$ has a finitely atomic representing measure $\mu$. The smallest possible number of atoms is called the Carath\'eodory number $\mathcal{C}_{\mathsf{A}}(s)$. The largest number $\mathcal{C}_{\mathsf{A}}(s)$ among all moment sequences $s$ is the Carath\'eodory number $\mathcal{C}_{\mathsf{A}}$. In this paper the Carath\'eodory numbers $\mathcal{C}_{\mathsf{A}}(s)$ and $\mathcal{C}_{\mathsf{A}}$ are studied. In the case of differentiable functions methods from differential geometry are used. The main emphasis is on real polynomials. For a large class of spaces of polynomials in one variable the number $\mathcal{C}_{\mathsf{A}}$ is determined. In the multivariate case we obtain some lower bounds and we use results on zeros of positive polynomials to derive upper bounds for the Carath\'eodory numbers.