In this paper, we propose a new \emph{dynamic compressed index} of $O(w)$ space for a dynamic text $T$, where $w = O(\min(z \log N \log^*M, N))$ is the size of the signature encoding of $T$, $z$ is the size of the Lempel-Ziv77 (LZ77) factorization of $T$, $N$ is the length of $T$, and $M \geq 3N$ is an integer that can be handled in constant time under word RAM model. Our index supports searching for a pattern $P$ in $T$ in $O(|P| f_{\mathcal{A}} + \log w \log |P| \log^* M (\log N + \log |P| \log^* M) + \mathit{occ} \log N)$ time and insertion/deletion of a substring of length $y$ in $O((y+ \log N\log^* M)\log w \log N \log^* M)$ time, where $f_{\mathcal{A}} = O(\min \{ \frac{\log\log M \log\log w}{\log\log\log M}, \sqrt{\frac{\log w}{\log\log w}} \})$. Also, we propose a new space-efficient LZ77 factorization algorithm for a given text of length $N$, which runs in $O(N f_{\mathcal{A}} + z \log w \log^3 N (\log^* N)^2)$ time with $O(w)$ working space.

Takaaki Nishimoto Tomohiro I Shunsuke Inenaga Hideo Bannai Masayuki Takeda

Given a pattern $P$ and a text $T$, both strings over a binary alphabet, the binary jumbled string matching problem consists in telling whether any permutation of $P$ occurs in $T$. The indexed version of this problem, i.e., preprocessing a string to efficiently answer such permutation queries, is hard and has been studied in the last few years. Currently the best bounds for this problem are $O(n^2/\log^2 n)$ (with O(n) space and O(1) query time) and $O(r^2\log r)$ (with O(|L|) space and $O(\log|L|)$ query time), where $r$ is the length of the run-length encoding of $T$ and $|L| = O(n)$ is the size of the index. In this paper we present new results for this problem. Our first result is an alternative construction of the index by Badkobeh et al. that obtains a trade-off between the space and the time complexity. It has $O(r^2\log k + n/k)$ complexity to build the index, $O(\log k)$ query time, and uses $O(n/k + |L|)$ space, where $k$ is a parameter. The second result is an $O(n^2 \log^2 w / w)$ algorithm (with O(n) space and O(1) query time), based on word-level parallelism where $w$ is the word size in bits.

Emanuele Giaquinta Szymon Grabowski

We describe a data structure, called a priority range tree, which accommodates fast orthogonal range reporting queries on prioritized points. Let $S$ be a set of $n$ points in the plane, where each point $p$ in $S$ is assigned a weight $w(p)$ that is polynomial in $n$, and define the rank of $p$ to be $r(p)=\lfloor \log w(p) \rfloor$. Then the priority range tree can be used to report all points in a three- or four-sided query range $R$ with rank at least $\lfloor \log w \rfloor$ in time $O(\log W/w + k)$, and report $k$ highest-rank points in $R$ in time $O(\log\log n + \log W/w' + k)$, where $W=\sum_{p\in S}{w(p)}$, $w'$ is the smallest weight of any point reported, and $k$ is the output size. All times assume the standard RAM model of computation. If the query range of interest is three sided, then the priority range tree occupies $O(n)$ space, otherwise $O(n\log n)$ space is used to answer four-sided queries. These queries are motivated by the Weber--Fechner Law, which states that humans perceive and interpret data on a logarithmic scale.

Michael T. Goodrich Darren Strash

A substring $u$ of a string $T$ is called a minimal unique substring (MUS) of $T$ if $u$ occurs exactly once in $T$ and any proper substring of $u$ occurs at least twice in $T$. A string $w$ is called a minimal absent word (MAW) of $T$ if $w$ does not occur in $T$ and any proper substring of $w$ occurs in $T$. In this paper, we study the problems of computing MUSs and MAWs in a sliding window over a given string $T$. We first show how the set of MUSs can change in a sliding window over $T$, and present an $O(n\log\sigma)$-time and $O(d)$-space algorithm to compute MUSs in a sliding window of width $d$ over $T$, where $\sigma$ is the maximum number of distinct characters in every window. We then give tight upper and lower bounds on the maximum number of changes in the set of MAWs in a sliding window over $T$. Our bounds improve on the previous results in [Crochemore et al., 2017].

Takuya Mieno Yuki Kuhara Tooru Akagi Yuta Fujishige Yuto Nakashima Shunsuke Inenaga Hideo Bannai Masayuki Takeda

Let $N\geq 2$ and $F:\mathbb{R}^N\to \mathbb{R} $ be the unique increasing radially symmetric function satisfying the minimal surface equation for graphs with the initial conditions $F(1)=0$ and $\lim_{r\to 1}F_r(r)=\infty;$ $r=|x|.$ We construct an ancient solution to Allen-Cahn equation $\tilde u_t = \Delta_{M} \tilde u + (1-{\tilde u}^2)\tilde u$ in $M\times(-\infty,0),$ where $M=\{(x, \pm F(|x|)):\;x\in\mathbb{R}^N,\;|x|\geq1\}$ is a $N$-dimensional catenoid in $\mathbb{R}^{N+1}$ and $\Delta_{M}$ is the Laplace Beltrami operator of $M.$ In particular, we construct a solution of the form $u(t,r,F(r))=u(t,r,-F(r))$ such that $$ u(t,r,F(r)) \approx \sum_{j=1}^k (-1)^{j-1}w(r-\rho_j(t)) - \frac 12 (1+ (-1)^{k}) \quad \hbox{ as } t\to -\infty, $$ where $w(s)$ is a solution of $w'' + (1-w^2)w=0$ with $w(\pm \infty)= \pm 1,$ given by $w(s) = \tanh \left(\frac s{\sqrt{2}} \right),$ and $$\rho_j(t)=\sqrt{-2(n-1)t}+\frac{1}{\sqrt{2}}\left(j-\frac{k+1}{2}\right)\log\left(\frac {|t|}{\log |t| }\right)+ O(1),\quad j=1,\ldots ,k.$$

Konstantinos T. Gkikas

In these proceedings a recent calculation of the last missing piece of the two-loop O(alpha alpha(s)) corrections to gamma t anti-t vertex at the t anti-t threshold due to the exchange of a W boson and a gluon is summarised. The calculation constitutes a building block of the top quark threshold production cross section at electron positron colliders.

Dirk Seidel

Let $\{b_{j}\}_{j=1}^{k}$ be meromorphic functions, and let $w$ be admissible meromorphic solutions of delay differential equation $$w'(z)=w(z)\left[\frac{P(z, w(z))}{Q(z,w(z))}+\sum_{j=1}^{k}b_{j}(z)w(z-c_{j})\right]$$ with distinct delays $c_{1}, \ldots, c_{k}\in\mathbb{C}\setminus\{0\},$ where the two nonzero polynomials $P(z, w(z))$ and $Q(z, w(z))$ in $w$ with meromorphic coefficients are prime each other. We obtain that if $\limsup_{r\rightarrow\infty}\frac{\log T(r, w)}{r}=0,$ then $$deg_{w}(P/Q)\leq k+2.$$ Furthermore, if $Q(z, w(z))$ has at least one nonzero root, then $deg_{w}(P)=deg_{w}(Q)+1\leq k+2;$ if all roots of $Q(z, w(z))$ are nonzero, then $deg_{w}(P)=deg_{w}(Q)+1\leq k+1;$ if $deg_{w}(Q)=0,$ then $deg_{w}(P)\leq 1.$\par In particular, whenever $deg_{w}(Q)=0$ and $deg_{w}(P)\leq 1$ and without the growth condition, any admissible meromorphic solution of the above delay differential equation (called Lenhart-Travis' type logistic delay differential equation) with reduced form can not be an entire function $w$ satisfying $\overline{N}(r, \frac{1}{w})=O(N(r, \frac{1}{w}));$ while if all coefficients are rational functions, then the condition $\overline{N}(r, \frac{1}{w})=O(N(r, \frac{1}{w}))$ can be omitted. Furthermore, any admissible meromorphic solution of the logistic delay differential equation (that is, for the simplest special case where $k=1$ and $deg_{w}(P/Q)=0$ ) satisfies that $N(r,w)$ and $T(r, w)$ have the same growth category. Some examples support our results.

Ling Xu Tingbin Cao

We have measured the half-life of $^{14}$O, a superallowed $(0^{+} \to 0^{+})$ $\beta$ decay isotope. The $^{14}$O was produced by the $^{12}$C($^{3}$He,n)$^{14}$O reaction using a carbon aerogel target. A low-energy ion beam of $^{14}$O was mass separated and implanted in a thin beryllium foil. The beta particles were counted with plastic scintillator detectors. We find $t_{1/2} = 70.696\pm 0.052$ s. This result is $1.5\sigma$ higher than an average value from six earlier experiments, but agrees more closely with the most recent previous measurement.

J. T. Burke P. A. Vetter S. J. Freedman B. K. Fujikawa W. T. Winter

The Levy transform of a Brownian motion B is the Brownian motion B't, the integral over (O,t) of sign of Bs with respect to dBs. Call T the corresponding transformation on the Wiener space W. We establish that a.s. the orbit of w in W under T is dense in W for the compact uniform convergence topology.

Marc Malric

Thermodynamic properties and structural aspects of the non-stoichiometric w\"ustite Fe 1-z O, and its modifications-the so-called pseudo-phases-as functions of composition z and equilibrium temperature are reviewed from 1960 to present (159 references). The focus is first put on the complexity of the equilibrium phase diagram. The first order transition W $\rightleftharpoons$ W' is specified on the boundary iron/ w\"ustite close to 1185 K. Transitions correlated to the modifications Wi at T(W) > 1185 K and W'j at 1185K < T(W') < T(W) (i and j =1,2,3) are reexamined. Structural determinations based on point defects and their clustering are recalled. A series of equilibria are developed, trying to justify the stabilization of the pseudo-phases, which can be interpreted in terms of transformation of defect clusters, or their mode of distribution (percolation, superstructure) including changes in electronic charge carriers.

Jean-Raymond Gavarri Claude Carel