Search

Computed Tomography (CT) has been widely adopted in medicine and it is increasingly being used in scientific and industrial applications. Parallelly, research in different mathematical areas concerning discrete inverse problems has led to the development of new sophisticated numerical solvers that can be applied in the context of CT. The Tomographic Iterative GPU-based Reconstruction (TIGRE) toolbox was born almost a decade ago precisely in the gap between mathematics and high performance computing for real CT data, providing user-friendly open-source software tools for image reconstruction. However, since its inception, the tools' features and codebase have had over a twenty-fold increase, and are now including greater geometric flexibility, a variety of modern algorithms for image reconstruction, high-performance computing features and support for other CT modalities, like proton CT. The purpose of this work is two-fold: first, it provides a structured overview of the current version of the TIGRE toolbox, providing appropriate descriptions and references, and serving as a comprehensive and peer-reviewed guide for the user; second, it is an opportunity to illustrate the performance of several of the available solvers showcasing real CT acquisitions, which are typically not be openly available to algorithm developers.

A permutation $\pi: [n] \rightarrow [n]$ is a Baxter permutation if and only if it does not contain either of the patterns $2-41-3$ and $3-14-2$. Baxter permutations are one of the most widely studied subclasses of general permutation due to their connections with various combinatorial objects such as plane bipolar orientations and mosaic floorplans, etc. In this paper, we introduce a novel succinct representation (i.e., using $o(n)$ additional bits from their information-theoretical lower bounds) for Baxter permutations of size $n$ that supports $\pi(i)$ and $\pi^{-1}(j)$ queries for any $i \in [n]$ in $O(f_1(n))$ and $O(f_2(n))$ time, respectively. Here, $f_1(n)$ and $f_2(n)$ are arbitrary increasing functions that satisfy the conditions $\omega(\log n)$ and $\omega(\log^2 n)$, respectively. This stands out as the first succinct representation with sub-linear worst-case query times for Baxter permutations. Additionally, we consider a subclass of Baxter permutations called \textit{separable permutations}, which do not contain either of the patterns $2-4-1-3$ and $3-1-4-2$. In this paper, we provide the first succinct representation of the separable permutation $\rho: [n] \rightarrow [n]$ of size $n$ that supports both $\rho(i)$ and $\rho^{-1}(j)$ queries in $O(1)$ time. In particular, this result circumvents Golynski's [SODA 2009] lower bound result for trade-offs between redundancy and $\rho(i)$ and $\rho^{-1}(j)$ queries. Moreover, as applications of these permutations with the queries, we also introduce the first succinct representations for mosaic/slicing floorplans, and plane bipolar orientations, which can further support specific navigational queries on them efficiently.

Tree covering is a technique for decomposing a tree into smaller-sized trees with desirable properties, and has been employed in various succinct data structures. However, significant hurdles stand in the way of a practical implementation of tree covering: a lot of pointers are used to maintain the tree-covering hierarchy and many indices for tree navigational queries consume theoretically negligible yet practically vast space. To tackle these problems, we propose a simple representation of tree covering using a balanced parenthesis representation. The key to the proposal is the observation that every micro tree splits into at most two intervals on the BP representation. Utilizing the representation, we propose several data structures that represent a tree and its tree cover, which consequently allow micro tree compression with arbitrary coding and efficient tree navigational queries. We also applied our data structure to average-case optimal RMQ by Munro et al.~[ESA 2021] and implemented the RMQ data structure. Our RMQ data structures spend less than $2n$ bits and process queries in a practical time on several settings of the performance evaluation, reducing the gap between theoretical space complexity and actual space consumption. We also implement tree navigational operations while using the same amount of space as the RMQ data structures. We believe the representation can be widely utilized for designing practically memory-efficient data structures based on tree covering., Comment: To appear in ESA 2024

We improve the worst-case information theoretic lower bound of Munro and Wu (ISAAC 2018) for $n-$vertex unlabeled chordal graphs when vertex leafage is bounded and leafage is unbounded. The class of unlabeled $k-$vertex leafage chordal graphs that consists of all chordal graphs with vertex leafage at most $k$ and unbounded leafage, denoted $\mathcal{G}_k$, is introduced for the first time. For $k>0$ in $o(n/\log n)$, we obtain a lower bound of $((k-1)n \log n -kn \log k - O(\log n))-$bits on the size of any data structure that encodes a graph in $\mathcal{G}_k$. Further, for every $k-$vertex leafage chordal graph $G$ such that for $k>1$ in $o(n^c), c >0$, we present a $((k-1)n \log n + o(kn \log n))-$bit succinct data structure, constructed using the succinct data structure for path graphs with $kn/2$ vertices. Our data structure supports adjacency query in $O(k \log n)$ time and using additional $2n \log n$ bits, an $O(k^2 d_v \log n + \log^2 n)$ time neighbourhood query where $d_v$ is degree of $v \in V$., Comment: 19 pages, 2 figure

Erd\H{o}s and West (Discrete Mathematics'85) considered the class of $n$ vertex intersection graphs which have a {\em $d$-dimensional} {\em $t$-representation}, that is, each vertex of a graph in the class has an associated set consisting of at most $t$ $d$-dimensional axis-parallel boxes. In particular, for a graph $G$ and for each $d \geq 1$, they consider $i_d(G)$ to be the minimum $t$ for which $G$ has such a representation. For fixed $t$ and $d$, they consider the class of $n$ vertex labeled graphs for which $i_d(G) \leq t$, and prove an upper bound of $(2nt+\frac{1}{2})d \log n - (n - \frac{1}{2})d \log(4\pi t)$ on the logarithm of size of the class. In this work, for fixed $t$ and $d$ we consider the class of $n$ vertex unlabeled graphs which have a {\em $d$-dimensional $t$-representation}, denoted by $\mathcal{G}_{t,d}$. We address the problem of designing a succinct data structure for the class $\mathcal{G}_{t,d}$ in an attempt to generalize the relatively recent results on succinct data structures for interval graphs (Algorithmica'21). To this end, for each $n$ such that $td^2$ is in $o(n / \log n)$, we first prove a lower bound of $(2dt-1)n \log n - O(ndt \log \log n)$-bits on the size of any data structure for encoding an arbitrary graph that belongs to $\mathcal{G}_{t,d}$. We then present a $((2dt-1)n \log n + dt\log t + o(ndt \log n))$-bit data structure for $\mathcal{G}_{t,d}$ that supports navigational queries efficiently. Contrasting this data structure with our lower bound argument, we show that for each fixed $t$ and $d$, and for all $n \geq 0$ when $td^2$ is in $o(n/\log n)$ our data structure for $\mathcal{G}_{t,d}$ is succinct. As a byproduct, we also obtain succinct data structures for graphs of bounded boxicity (denoted by $d$ and $t = 1$) and graphs of bounded interval number (denoted by $t$ and $d=1$) when $td^2$ is in $o(n/\log n)$., Comment: 21 pages, 5 figures

Given a directed edge-weighted graph $G=(V, E)$ with beer vertices $B\subseteq V$, a beer path between two vertices $u$ and $v$ is a path between $u$ and $v$ that visits at least one beer vertex in $B$, and the beer distance between two vertices is the shortest length of beer paths. We consider \emph{indexing problems} on beer paths, that is, a graph is given a priori, and we construct some data structures (called indexes) for the graph. Then later, we are given two vertices, and we find the beer distance or beer path between them using the data structure. For such a scheme, efficient algorithms using indexes for the beer distance and beer path queries have been proposed for outerplanar graphs and interval graphs. For example, Bacic et al. (2021) present indexes with size $O(n)$ for outerplanar graphs and an algorithm using them that answers the beer distance between given two vertices in $O(\alpha(n))$ time, where $\alpha(\cdot)$ is the inverse Ackermann function; the performance is shown to be optimal. This paper proposes indexing data structures and algorithms for beer path queries on general graphs based on two types of graph decomposition: the tree decomposition and the triconnected component decomposition. We propose indexes with size $O(m+nr^2)$ based on the triconnected component decomposition, where $r$ is the size of the largest triconnected component. For a given query $u,v\in V$, our algorithm using the indexes can output the beer distance in query time $O(\alpha(m))$. In particular, our indexing data structures and algorithms achieve the optimal performance (the space and the query time) for series-parallel graphs, which is a wider class of outerplanar graphs., Comment: 25 pages, 9 figures

OJ 287 is a BL Lacertae type quasar in which the active galactic nucleus (AGN) outshines the host galaxy by an order of magnitude. The only exception to this may be at minimum light when the AGN activity is so low that the host galaxy may make quite a considerable contribution to the photometric intensity of the source. Such a dip or a fade in the intensity of OJ 287 occurred in November 2017, when its brightness was about 1.75 magnitudes lower than the recent mean level. We compare the observations of this fade with similar fades in OJ 287 observed earlier in 1989, 1999, and 2010. It appears that there is a relatively strong reddening of the B$-$V colours of OJ 287 when its V-band brightness drops below magnitude 17. Similar changes are also seen V$-$R, V$-$I, and R$-$I colours during these deep fades. These data support the conclusion that the total magnitude of the host galaxy is $V=18.0 \pm 0.3$, corresponding to $M_{K}=-26.5 \pm 0.3$ in the K-band. This is in agreement with the results, obtained using the integrated surface brightness method, from recent surface photometry of the host. These results should encourage us to use the colour separation method also in other host galaxies with strongly variable AGN nuclei. In the case of OJ 287, both the host galaxy and its central black hole are among the biggest known, and its position in the black hole mass-galaxy mass diagram lies close to the mean correlation., Comment: 8 pages, 4 figures, accepted for publication in MNRAS

Morphology of nova ejecta is essential for fully understanding the physical processes involved in nova eruptions. We studied the 3D morphology of the expanding ejecta of the extremely slow nova V1280 Sco with a unique light curve. Synthetic line profile spectra were compared to the observed [O III] 4959, 5007 and [N II] 5755 emission line profiles in order to find the best-fit morphology, inclination angle, and maximum expansion velocity of the ejected shell. We derive the best fitting expansion velocity, inclination, and squeeze as $V_{\rm exp} = 2100^{+100}_{-100}$ \,km\,s$^{-1}$, $i = 80^{+1}_{-3}$ deg, and $squ = 1.0^{+0.0}_{-0.1}$ using [O III] line profiles, and $V_{\rm exp} = 1600^{+100}_{-100}$ \,km\,s$^{-1}$, $i = 81^{+2}_{-4}$ deg, and $squ = 1.0^{+0.0}_{-0.1}$ using [N II] 5755 line profile. A high inclination angle is consistent with the observational results showing multiple absorption lines originating from clumpy gases which are produced in dense and slow equatorially focused outflows. Based on additional observational features such as optical flares near the maximum light and dust formation on V1280 Sco, a model of internal shock interaction between slow ejecta and fast wind proposed for the $\gamma$-ray emission detected in other novae seems to be applicable to this extremely slow and peculiar nova. Increasing the sample size of novae whose morphology is studied will be helpful in addressing long-standing mysteries in novae such as the dominant energy source to power the optical light at the maximum, optical flares near the maximum, clumpiness of the ejecta, and dust formation., Comment: 21 pages, 8 figures, accepted for publication in ApJ

We consider the problem of designing a succinct data structure for {\it path graphs} (which are a proper subclass of chordal graphs and a proper superclass of interval graphs) on $n$ vertices while supporting degree, adjacency, and neighborhood queries efficiently. We provide the following two solutions for this problem: - an $n \log n+o(n \log n)$-bit succinct data structure that supports adjacency query in $O(\log n)$ time, neighborhood query in $O(d \log n)$ time and finally, degree query in $\min\{O(\log^2 n), O(d \log n)\}$ where $d$ is the degree of the queried vertex. - an $O(n \log^2 n)$-bit space-efficient data structure that supports adjacency and degree queries in $O(1)$ time, and the neighborhood query in $O(d)$ time where $d$ is the degree of the queried vertex. Central to our data structures is the usage of the classical heavy path decomposition by Sleator and Tarjan~\cite{ST}, followed by a careful bookkeeping using an orthogonal range search data structure using wavelet trees~\cite{Makinen2007} among others, which maybe of independent interest for designing succinct data structures for other graph classes., Comment: 39 pages, 5 figure, 6 sections, 2 tables

The run-length compressed Burrows-Wheeler transform (RLBWT) used in conjunction with the backward search introduced in the FM index is the centerpiece of most compressed indexes working on highly-repetitive data sets like biological sequences. Compared to grammar indexes, the size of the RLBWT is often much bigger, but queries like counting the occurrences of long patterns can be done much faster than on any existing grammar index so far. In this paper, we combine the virtues of a grammar with the RLBWT by building the RLBWT on top of a special grammar based on induced suffix sorting. Our experiments reveal that our hybrid approach outperforms the classic RLBWT with respect to the index sizes, and with respect to query times on biological data sets for sufficiently long patterns.

We design succinct encodings of {\it series-parallel, block-cactus} and {\it 3-leaf power} graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood {\it optimally} in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds.

We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency, and neighborhood efficiently for intersection graphs on a circle, which include graph classes such as {\it circle graphs}, {\it $k$-polygon-circle graphs}, {\it circle-trapezoid graphs}, {\it trapezoid graphs}. The degree query reports the number of incident edges to a given vertex, the adjacency query asks if there is an edge between two given vertices, and the neighborhood query enumerates all the neighbors of a given vertex. We first prove a general lower bound for these intersection graph classes and then present a uniform approach that lets us obtain matching lower and upper bounds for representing each of these graph classes. More specifically, our lower bound proofs use a unified technique to produce tight bounds for all these classes, and this is followed by our data structures which are also obtained from a unified representation method to achieve succinctness for each class. In addition, we prove a lower bound of space for representing {\it trapezoid} graphs and give a succinct navigational oracle for this class of graphs.

We constructed a comprehensive model atom for NeI -- NeII using the most up-to-date atomic data available and evaluated the non-local thermodynamic equilibrium (NLTE) line formation for NeI and NeII in classical 1D models representing the atmospheres of B-type stars. We find that the large NLTE strengthening of the NeI lines corresponding to the 2p$^5$3p $-$ 2p$^5$3s transitions array occurs due to extremely small photoionization cross-sections of 2p$^5$3s levels that leads to strong overpopulation of these levels relative to their LTE populations. The deviations from LTE for the most NeII lines are small and do not exceed 0.11~dex in the absolute value. We analysed 20 lines of NeI and 13 lines of NeII for twenty-four B-type stars in the temperature range of 10\,400 $\le$ \Teff\ $\le$ 33\,400~K. For five stars, the NLTE leads to consistent abundances of NeI and NeII, while the difference in LTE abundance can reach up to 0.50~dex. The using of the experimental oscillator strengths recently measured by Piracha et al. (2015) leads to smaller line-by-line scatter for the most investigated stars. The averaged neon abundance in twenty-four B-type stars in solar neighborhood is 8.02$\pm$0.05. This value may provide indirect constraints on solar photospheric neon abundance., Comment: 20 pages, 9 figures, accepted to Astrophysical Journal

Zero-suppressed Binary Decision Diagrams (ZDDs) are data structures for representing set families in a compressed form. With ZDDs, many valuable operations on set families can be done in time polynomial in ZDD size. In some cases, however, the size of ZDDs for representing large set families becomes too huge to store them in the main memory. This paper proposes top ZDD, a novel representation of ZDDs which uses less space than existing ones. The top ZDD is an extension of top tree, which compresses trees, to compress directed acyclic graphs by sharing identical subgraphs. We prove that navigational operations on ZDDs can be done in time poly-logarithmicin ZDD size, and show that there exist set families for which the size of the top ZDD is exponentially smaller than that of the ZDD. We also show experimentally that our top ZDDs have smaller size than ZDDs for real data., Comment: 19 pages; Accepted for SEA2020

We report the results of decade-long (2008-2018) $\gamma$-ray to 1 GHz radio monitoring of the blazar 3C 279, including GASP/WEBT, $\it{Fermi}$ and $\it{Swift}$ data, as well as polarimetric and spectroscopic data. The X-ray and $\gamma$-ray light curves correlate well, with no delay > 3 hours, implying general co-spatiality of the emission regions. The $\gamma$-ray-optical flux-flux relation changes with activity state, ranging from a linear to a more complex dependence. The behaviour of the Stokes parameters at optical and radio wavelengths, including 43 GHz VLBA images, supports either a predominantly helical magnetic field or motion of the radiating plasma along a spiral path. Apparent speeds of emission knots range from 10 to 37c, with the highest values requiring bulk Lorentz factors close to those needed to explain $\gamma$-ray variability on very short time scales. The Mg II emission line flux in the `blue' and `red' wings correlates with the optical synchrotron continuum flux density, possibly providing a variable source of seed photons for inverse Compton scattering. In the radio bands we find progressive delays of the most prominent light curve maxima with decreasing frequency, as expected from the frequency dependence of the $\tau=1$ surface of synchrotron self-absorption. The global maximum in the 86 GHz light curve becomes less prominent at lower frequencies, while a local maximum, appearing in 2014, strengthens toward decreasing frequencies, becoming pronounced at $\sim5$ GHz. These tendencies suggest different Doppler boosting of stratified radio-emitting zones in the jet., Comment: 21 pages, 18 figures, accepted for publication in MNRAS

We present a multiwavelength study of the flat-spectrum radio quasar CTA 102 during 2013-2017. We use radio-to-optical data obtained by the Whole Earth Blazar Telescope, 15 GHz data from the Owens Valley Radio Observatory, 91 and 103 GHz data from the Atacama Large Millimeter Array, near-infrared data from the Rapid Eye Monitor telescope, as well as data from the Swift (optical-UV and X-rays) and Fermi ($\gamma$ rays) satellites to study flux and spectral variability and the correlation between flux changes at different wavelengths. Unprecedented $\gamma$-ray flaring activity was observed during 2016 November-2017 February, with four major outbursts. A peak flux of (2158 $\pm$ 63)$\times$10$^{-8}$ ph cm$^{-2}$ s$^{-1}$, corresponding to a luminosity of (2.2 $\pm$ 0.1)$\times$10$^{50}$ erg s$^{-1}$, was reached on 2016 December 28. These four $\gamma$-ray outbursts have corresponding events in the near-infrared, optical, and UV bands, with the peaks observed at the same time. A general agreement between X-ray and $\gamma$-ray activity is found. The $\gamma$-ray flux variations show a general, strong correlation with the optical ones with no time lag between the two bands and a comparable variability amplitude. This $\gamma$-ray/optical relationship is in agreement with the geometrical model that has successfully explained the low-energy flux and spectral behaviour, suggesting that the long-term flux variations are mainly due to changes in the Doppler factor produced by variations of the viewing angle of the emitting regions. The difference in behaviour between radio and higher energy emission would be ascribed to different viewing angles of the jet regions producing their emission., Comment: 24 pages, 18 figures, and 4 tables. Accepted for publication in Monthly Notices of the Royal Astronomical Society

We present a model atom for C I - C II - C III - C IV using the most up-to-date atomic data and evaluated the non-local thermodynamic equilibrium (NLTE) line formation in classical 1D atmospheric models of O-B-type stars. Our models predict the emission lines of C II 9903~\AA\ and 18535~\AA\ to appear at effective temperature \Teff~$\geq$~17\,500~K, those of C II 6151~\AA\ and 6461~\AA\ to appear at \Teff~$>$~25\,000~K, and those of C III 5695, 6728--44, 9701--17~\AA\ to appear at \Teff~$\geq$~35\,000~K (log~$g$=4.0). Emission occurs in the lines of minority species, where the photoionization-recombination mechanism provides a depopulation of the lower levels to a greater extent than the upper levels. For C II 9903 and 18535~\AA, the upper levels are mainly populated from C III reservoir through the Rydberg states. For C III 5695 and 6728--44~\AA, the lower levels are depopulated due to photon losses in UV transitions at 885, 1308, and 1426--28~\AA\ which become optically thin in the photosphere. We analysed the lines of C I, C II, C III, and C IV for twenty-two O-B-type stars with temperature range between 15\,800 $\leq$~\Teff~$\leq$ 38\,000~K. Abundances from emission lines of C I, C II and C III are in agreement with those from absorption ones for most of the stars. We obtained log~$\epsilon_{\rm C}$=8.36$\pm$0.08 from twenty B-type stars, that is in line with the present-day Cosmic Abundance Standard. The obtained carbon abundances in 15~Mon and HD~42088 from emission and absorption lines are 8.27$\pm$0.11 and 8.31$\pm$0.11, respectively., Comment: 22 pages, 11 figures

We consider the range mode problem where given a sequence and a query range in it, we want to find items with maximum frequency in the range. We give time- and space- efficient algorithms for this problem. Our algorithms are efficient for small maximum frequency cases. We also consider a natural generalization of the problem: the range mode enumeration problem, for which there has been no known efficient algorithms. Our algorithms have query time complexities which is linear to the output size plus small terms.

Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information-theoretically optimal number of bits along with supporting queries on them efficiently. Towards this goal, we first design a succinct data structure for representing any deterministic finite automaton $\mathcal{D}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $(\sigma-1) n\log n + O(n \log \sigma)$ bits of space, which can determine, given an input string $x$ over $\Sigma$, whether $\mathcal{D}$ accepts $x$ in $O(|x| \log \sigma)$ time, using constant words of working space. When the input deterministic finite automaton is acyclic, not only we can improve the above space-bound significantly to $(\sigma -1) (n-1)\log n+ 3n + O(\log^2 \sigma) + o(n)$ bits, we also obtain optimal query time for string acceptance checking. More specifically, using our succinct representation, we can check if a given input string $x$ can be accepted by the acyclic deterministic finite automaton using time proportional to the length of $x$, hence, the optimal query time. We also exhibit a succinct data structure for representing a non-deterministic finite automaton $\mathcal{N}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $\sigma n^2+n$ bits of space, such that given an input string $x$, we can decide whether $\mathcal{N}$ accepts $x$ efficiently in $O(n^2|x|)$ time. Finally, we also provide time and space-efficient algorithms for performing several standard operations such as union, intersection, and complement on the languages accepted by deterministic finite automata.

We present linear time {\it in-place} algorithms for several basic and fundamental graph problems including the well-known graph search methods (like depth-first search, breadth-first search, maximum cardinality search), connectivity problems (like biconnectivity, $2$-edge connectivity), decomposition problem (like chain decomposition) among various others, improving the running time (by polynomial multiplicative factor) of the recent results of Chakraborty et al. [ESA, 2018] who designed $O(n^3 \lg n)$ time in-place algorithms for a strict subset of the above mentioned problems. The running times of all our algorithms are essentially optimal as they run in linear time. One of the main ideas behind obtaining these algorithms is the detection and careful exploitation of sortedness present in the input representation for any graph without loss of generality. This observation alone is powerful enough to design some basic linear time in-place algorithms, but more non-trivial graph problems require extra techniques which, we believe, may find other applications while designing in-place algorithms for different graph problems in the future.

We consider the problem of compactly representing the Depth First Search (DFS) tree of a given undirected or directed graph having $n$ vertices and $m$ edges while supporting various DFS related queries efficiently in the RAM with logarithmic word size. We study this problem in two well-known models: {\it indexing} and {\it encoding} models. While most of these queries can be supported easily in constant time using $O(n \lg n)$ bits\footnote{We use $\lg$ to denote logarithm to the base $2$.} of extra space, our goal here is, more specifically, to beat this trivial $O(n \lg n)$ bit space bound, yet not compromise too much on the running time of these queries. In the {\it indexing} model, the space bound of our solution involves the quantity $m$, hence, we obtain different bounds for sparse and dense graphs respectively. In the {\it encoding} model, we first give a space lower bound, followed by an almost optimal data structure with extremely fast query time. Central to our algorithm is a partitioning of the DFS tree into connected subtrees, and a compact way to store these connections. Finally, we also apply these techniques to compactly index the shortest path structure, biconnectivity structures among others., Comment: 23 pages, Preliminary version of this paper will appear in MFCS 2019

We present a list of weak emission lines (WELs) observed in a sharp-lined B3 V star {\iota} Her (HD 160762) using high resolution (R = 65000) and high SN (~1300) spectral data. The list covers a spectral region between 4900A and 10000A. We register 207 WELs in this star and identified 190 lines including ten ions (nine elements). Emission lines of C II, N I, Cr II, Mn II, and Ni II have been identified among normal B-type stars for the first time. 17 emission lines remain unidentified. We compare our list with the published list of WELs for 3 Cen A (Wahlgren and Hubrig 2004) and found that numbers of detected emission lines reflect differences in abundance between these two stars. We detect 13 C I emission lines in iota Her (normal in C), while only one C I emission line is found in 3 Cen A (deficient in C). Many emission lines of P II and Cu II have been detected in 3 Cen A (overabundant in both P and Cu), while no emission line of these ions has been found in {\iota} Her. Many emission lines of Fe II are visible in the shorter wavelength side of 6000 A in iota Her, while these emission lines are missing in 3 Cen A. Close inspections of spectral data of 3 Cen A reveal that apparently missing Fe II lines appear as absorption lines in this star. Because these two stars have nearly the same atmospheric parameters (Teff and log g), a physical interpretation which is independent on these two parameters is needed to account for this observation., Comment: 13 pages, 7 figures

Blazar OJ287 exhibits large thermal flares at least twice every 12 years. The times of these flares have been predicted successfully using the model of a quasi-Keplerian eccentric black hole binary where the secondary impacts the accretion disk of the primary, creating the thermal flares. New measurements of the historical light curve have been combined with the observations of the 2015 November/December flare to identify the impact record since year 1886, and to constrain the orbit of the binary. The orbit solution shows that the binary period, now 12.062 year, is decreasing at the rate of 36 days per century. This corresponds to an energy loss to gravitational waves that is 6.5 +- 4 % less than the rate predicted by the standard quadrupolar gravitational wave (GW) emission. We show that the difference is due to higher order gravitational radiation reaction terms that include the dominant order tail contributions., Comment: to appear in the Proceedings of Gravitational Wave Astrophysics: Early Results from Gravitational Wave Searches and Electromagnetic Counterparts. eds. Gabriela Gonzales and Robert Hynes

Abundances of 21 elements in two 3He stars HD 185330 and 3 Cen A have been analysed relative to the well studied sharp-lined B3 V star iota Her. Six elements (P, Ti, Mn, Fe, Ni, and Br) are over-abundant in these two peculiar stars, while six elements (C, O, Mg, Al, S, and Cl) are under-abundant. Absorption lines of the two rarely observed heavy elements Br II and Kr II are detected in both stars and these elements are both over-abundant. The centroid wavelengths of the Ca II infrared triplet lines in these stars are red-shifted relative to those lines in iota Her and the presence of heavy isotopes of Ca (mass number 44 - 46) in these two stars are confirmed. In spite of these similarities, there are several remarkable differences in the abundance pattern between these two stars. N is under-abundant in HD 185330, as in many Hg-Mn stars, while it is significantly over-abundant in 3 Cen A. P and Ga are both over-abundant in 3 Cen A, while only P is over-abundant and no trace of absorption line of Ga II can be found in HD 185330. Large over-abundances of Kr and Xe are found in both stars, while the abundance ratios Kr / Xe are significantly different between them (-1.4 dex in HD 185330 and +1.2 dex in 3 Cen A). Some physical explanations are needed to account for these qualitative differences., Comment: 12 pages,13 figures, accepted for publication in PASJ

This study considers the (soft) capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph $G=(V,E)$, which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex $v$ in the cover, the number of $v$'s incident edges covered by the copy is up to a given capacity of $v$. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with $O(\log n / \epsilon)$ amortized update time, where $n$ is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a nonuniform and unsplittable demand, and (2) the more general capacitated set cover problem.

We present the results of our power spectral density analysis for the BL Lac object OJ\,287, utilizing the {\it Fermi}-LAT survey at high-energy $\gamma$-rays, {\it Swift}-XRT in X-rays, several ground-based telescopes and the {\it Kepler} satellite in the optical, and radio telescopes at GHz frequencies. The light curves are modeled in terms of continuous-time auto-regressive moving average (CARMA) processes. Owing to the inclusion of the {\it Kepler} data, we were able to construct \emph{for the first time} the optical variability power spectrum of a blazar without any gaps across $\sim6$ dex in temporal frequencies. Our analysis reveals that the radio power spectra are of a colored-noise type on timescales ranging from tens of years down to months, with no evidence for breaks or other spectral features. The overall optical power spectrum is also consistent with a colored noise on the variability timescales ranging from 117 years down to hours, with no hints of any quasi-periodic oscillations. The X-ray power spectrum resembles the radio and optical power spectra on the analogous timescales ranging from tens of years down to months. Finally, the $\gamma$-ray power spectrum is noticeably different from the radio, optical, and X-ray power spectra of the source: we have detected a characteristic relaxation timescale in the {\it Fermi}-LAT data, corresponding to $\sim 150$\,days, such that on timescales longer than this, the power spectrum is consistent with uncorrelated (white) noise, while on shorter variability timescales there is correlated (colored) noise., Comment: ApJ accepted

Previously unrecognized weak emission lines originating from high excitation states of Si II (12.84 eV) and Al II (13.08 eV) are detected in the red region spectra of slowly rotating early B-type stars. We surveyed high resolution spectra of 35 B-type stars covering spectral sub-types between B1 and B7 near the main sequence and found the emission line of SiII at 6239.6 A in all 13 stars having spectral sub-types B2 and B2.5. There are 17 stars belonging to sub-type B3 and seven stars among them are found to show the emission line of Si II. The emission line of Al II at 6243.4 A is detected in a narrower temperature range (Teff between 19000K and 23000 K) in nine stars. Both of these emission lines are not detected in cooler (Teff < 16000 K) stars in our sample. The emission line of Si II at 6239.6 A shows a single-peaked and symmetric profile and the line center has no shift in wavelength with respect to those of low excitation absorption lines of Si II. Measured half width of the emission line is the same as those of rotationally broadened low excitation absorption lines of Si II. These observations imply that the emitting gas is not circumstellar origin, but is located at the outermost layer of the atmosphere, covering the whole stellar surface and co-rotates with the star., Comment: 6 pages, 4 figures, 2 tables, accepted for publication in Publ. Astron. Soc. Japan

We carried out a pilot campaign of radio and optical band intra-day variability (IDV) observations of five blazars (3C66A, S5 0716+714, OJ287, B0925+504, and BL Lacertae) on December 18--21, 2015 by using the radio telescope in Effelsberg (Germany) and several optical telescopes in Asia, Europe, and America. After calibration, the light curves from both 5 GHz radio band and the optical R band were obtained, although the data were not smoothly sampled over the sampling period of about four days. We tentatively analyse the amplitudes and time scales of the variabilities, and any possible periodicity. The blazars vary significantly in the radio (except 3C66A and BL Lacertae with only marginal variations) and optical bands on intra- and inter-day time scales, and the source B0925+504 exhibits a strong quasi-periodic radio variability. No significant correlation between the radio- and optical-band variability appears in the five sources, which we attribute to the radio IDV being dominated by interstellar scintillation whereas the optical variability comes from the source itself. However, the radio- and optical-band variations appear to be weakly correlated in some sources and should be investigated based on well-sampled data from future observations., Comment: 6 pages, 6 figures, accepted by MNRAS

We present a framework facilitating the implementation and comparison of text compression algorithms. We evaluate its features by a case study on two novel compression algorithms based on the Lempel-Ziv compression schemes that perform well on highly repetitive texts.

OJ287 is a quasi-periodic quasar with roughly 12 year optical cycles. It displays prominent outbursts which are predictable in a binary black hole model. The model predicted a major optical outburst in December 2015. We found that the outburst did occur within the expected time range, peaking on 2015 December 5 at magnitude 12.9 in the optical R-band. Based on Swift/XRT satellite measurements and optical polarization data, we find that it included a major thermal component. Its timing provides an accurate estimate for the spin of the primary black hole, chi = 0.313 +- 0.01. The present outburst also confirms the established general relativistic properties of the system such as the loss of orbital energy to gravitational radiation at the 2 % accuracy level and it opens up the possibility of testing the black hole no-hair theorem with a 10 % accuracy during the present decade.

In this paper, we present a new data structure called the packed compact trie (packed c-trie) which stores a set $S$ of $k$ strings of total length $n$ in $n \log\sigma + O(k \log n)$ bits of space and supports fast pattern matching queries and updates, where $\sigma$ is the size of an alphabet. Assume that $\alpha = \log_\sigma n$ letters are packed in a single machine word on the standard word RAM model, and let $f(k,n)$ denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores $k$ integers from universe $[1,n]$ in $O(k \log n)$ bits of space. Then, given a string of length $m$, our packed c-tries support pattern matching queries and insert/delete operations in $O(\frac{m}{\alpha} f(k,n))$ worst-case time and in $O(\frac{m}{\alpha} + f(k,n))$ expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. As an application of our packed c-trie, we show that the sparse suffix tree for a string of length $n$ over prefix codes with $k$ sampled positions, such as evenly-spaced and word delimited sparse suffix trees, can be constructed online in $O((\frac{n}{\alpha} + k) f(k,n))$ worst-case time and $O(\frac{n}{\alpha} + k f(k,n))$ expected time with $n \log \sigma + O(k \log n)$ bits of space. When $k = O(\frac{n}{\alpha})$, by using the state-of-the-art dynamic predecessor/successor data structures, we obtain sub-linear time construction algorithms using only $O(\frac{n}{\alpha})$ bits of space in both cases. We also discuss an application of our packed c-tries to online LZD factorization., Comment: 10 pages, 2 figures

We report spectroscopic observations of the resonance lines of singly ionized $^{7}$Be in the blue-shifted absorption line systems found in the post-outburst spectra of two classical novae -- V5668 Sgr (Nova Sagittarii 2015 No.2) and V2944 Oph (Nova Ophiuchi 2015). The unstable isotope, $^{7}$Be, should has been created during the thermonuclear runaway (TNR) of these novae and decays to form $^{7}$Li within a short period (a half-life of 53.22 days). Confirmations of $^{7}$Be are the second and the third ones following the first case found in V339 Del by Tajitsu et al. (2015). The blue-shifted absorption line systems in both novae are clearly divided into two velocity components, both of which contain $^{7}$Be. This means that the absorbing gases in both velocity components consist of products of TNR. We estimate amounts of $^{7}$Be produced during outbursts of both novae and conclude that significant $^{7}$Li should have been created. These findings strongly suggest that the explosive production of $^{7}$Li via the reaction $^{3}$He($\alpha$,$\gamma$)$^{7}$Be and subsequent decay to $^{7}$Li occurs frequently among classical novae and contributes to the process of the Galactic Li enrichment., Comment: 8 pages, 6 figures, accepted for publication in ApJ

We show that both the Lempel Ziv 77- and the 78-factorization of a text of length $n$ on an integer alphabet of size $\sigma$ can be computed in $O(n \lg \lg \sigma)$ time (linear time if we allow randomization) using $O(n \lg \sigma)$ bits of working space. Given that a compressed representation of the suffix tree is loaded into RAM, we can compute both factorizations in $O(n)$ time using $z \lg n + O(n)$ bits of space, where $z$ is the number of factors.

The origin of lithium (Li) and its production process have long been an unsettled question in cosmology and astrophysics. Candidates environments of Li production events or sites suggested by previous studies include big bang nucleosynthesis, interactions of energetic cosmic rays with interstellar matter, evolved low mass stars, novae, and supernova explosions. Chemical evolution models and observed stellar Li abundances suggest that at least half of the present Li abundance may have been produced in red giants, asymptotic giant branch (AGB) stars, and novae. However, no direct evidence for the supply of Li from stellar objects to the Galactic medium has yet been found. Here we report on the detection of highly blue-shifted resonance lines of the singly ionized radioactive isotope of beryllium, $^{7}$Be, in the near ultraviolet (UV) spectra of the classical nova V339 Del (Nova Delphini 2013). Spectra were obtained 38 to 48 days after the explosion. $^{7}$Be decays to form $^{7}$Li within a short time (half-life 53.22 days). The spectroscopic detection of this fragile isotope implies that it has been created during the nova explosion via the reaction $^{3}\mbox{He}(\alpha,\gamma)^{7}\mbox{Be}$, and supports the theoretical prediction that a significant amount of $^{7}$Li could be produced in classical nova explosions. This finding opens a new way to explore $^{7}$Li production in classical novae and provides a clue to the mystery of the Galactic evolution of lithium., Comment: 28 pages, 6 figures, published in Nature

The de Bruijn graph $G_K$ of a set of strings $S$ is a key data structure in genome assembly that represents overlaps between all the $K$-length substrings of $S$. Construction and navigation of the graph is a space and time bottleneck in practice and the main hurdle for assembling large, eukaryote genomes. This problem is compounded by the fact that state-of-the-art assemblers do not build the de Bruijn graph for a single order (value of $K$) but for multiple values of $K$. More precisely, they build $d$ de Bruijn graphs, each with a specific order, i.e., $G_{K_1}, G_{K_2}, ..., G_{K_d}$. Although, this paradigm increases the quality of the assembly produced, it increases the memory by a factor of $d$ in most cases. In this paper, we show how to augment a succinct de Bruijn graph representation by Bowe et al. (Proc. WABI, 2012) to support new operations that let us change order on the fly, effectively representing all de Bruijn graphs of order up to some maximum $K$ in a single data structure. Our experiments show our variable-order de Bruijn graph only modestly increases space usage, construction time, and navigation time compared to a single order graph., Comment: Conference submission, 10 pages, +minor corrections

MEGAHIT is a NGS de novo assembler for assembling large and complex metagenomics data in a time- and cost-efficient manner. It finished assembling a soil metagenomics dataset with 252Gbps in 44.1 hours and 99.6 hours on a single computing node with and without a GPU, respectively. MEGAHIT assembles the data as a whole, i.e., it avoids pre-processing like partitioning and normalization, which might compromise on result integrity. MEGAHIT generates 3 times larger assembly, with longer contig N50 and average contig length than the previous assembly. 55.8% of the reads were aligned to the assembly, which is 4 times higher than the previous. The source code of MEGAHIT is freely available at https://github.com/voutcn/megahit under GPLv3 license., Comment: 2 pages, 2 tables, 1 figure, submitted to Oxford Bioinformatics as an Application Note

We introduce a new concept of a subgraph class called a superbubble for analyzing assembly graphs, and propose an efficient algorithm for detecting it. Most assembly algorithms utilize assembly graphs like the de Bruijn graph or the overlap graph constructed from reads. From these graphs, many assembly algorithms first detect simple local graph structures (motifs), such as tips and bubbles, mainly to find sequencing errors. These motifs are easy to detect, but they are sometimes too simple to deal with more complex errors. The superbubble is an extension of the bubble, which is also important for analyzing assembly graphs. Though superbubbles are much more complex than ordinary bubbles, we show that they can be efficiently enumerated. We propose an average-case linear time algorithm (i.e., O(n+m) for a graph with n vertices and m edges) for graphs with a reasonable model, though the worst-case time complexity of our algorithm is quadratic (i.e., O(n(n+m))). Moreover, the algorithm is practically very fast: Our experiments show that our algorithm runs in reasonable time with a single CPU core even against a very large graph of a whole human genome., Comment: Peer-reviewed and presented as part of the 13th Workshop on Algorithms in Bioinformatics (WABI2013)

We present multi-color light curves and optical spectra of V1280 Scorpii obtained from 2007 to 2012. It is shown that V1280 Sco is the extremely slow nova and the mass of white dwarf appears to be $\sim$ 0.6 M$\odot$ or lower. Blue-shifted multiple absorption lines of Na {\sc i} D, Ca {\sc ii} HK, and He {\sc i*} are detected on high-resolution spectra. We also discuss that an approach using metastable He absorption lines is useful to investigate structures of nova shells., Comment: 4 pages, 3 figures, to appear in Stella Novae: Future and Past Decades, P. A. Woudt & V. A. R. M. Ribeiro (eds), ASPCS

We carried out optical high-dispersion spectroscopic monitoring of the Be disk in a Be/X-ray binary A 0535+262/V725 Tau from 2009 to 2012, covering two giant outbursts and several normal outbursts. This monitoring was performed in order to investigate variabilities of the Be disk due to the interaction with the neutron star in recent X-ray active phase from 2008 to 2011. Such variabilities give a clue to uncleared detailed mechanism for very bright X-ray outbursts, which are unique to some Be/X-ray binaries with relatively wide and eccentric orbit. In the previous letter (Moritani et al. 2011), a brief overview of line profile variabilities around the 2009 giant outburst was given and the possibility of a warped Be disk was discussed. In this paper, a full analysis of the Halpha line profiles as well as other line profiles is carried out. A bright blue component, or blue "shoulder", showing up after periastron indicates the presence of a dense gas stream toward the neutron star, which is associated with observed outbursts. We re-analyze the Halpha line profiles before 2009 (down to 2005) in order to investigate the variability of the the disk structure in the innermost region, which seems to have detached from the Be star surface by 2008. A redshifted enhanced component is remarkable in all emission lines observed around the 2009 giant outburst, occasionally forming a triple peak. These features indicate that the Be disk was warped in X-ray active phase. We estimate the position of the warped region from fitting the radial velocity of the redshifted enhanced component of Halpha, and find that it was very close to the periastron when two giant outbursts in 2009 and 2011 and a bright normal outburst in 2010 March occurred. These facts strongly suggest that the warped Be disk triggered these giant outbursts., Comment: accepted to PASJ

In an attempt to carry out a systematic study on the behavior of the photospheric abundances of Li, C, and O (along with Fe) for Hyades main-sequence stars in the T_eff range of ~5000-7000K, we conducted an extensive spectrum-synthesis analysis applied to four spectral regions (comprising lines of Fe-group elements, Li I 6708 line, C I 7111-7119 lines, and O I 6156-8 lines) based on the high-dispersion spectra of 68 selected F-G type stars belonging to this cluster. The abundances of C and O turned out to be fairly uniform in a marginally supersolar level such like the case of Fe: <[C/H]> = +0.15 (sigma = 0.08), <[O/H]> = +0.22 (sigma = 0.14), and <[Fe/H]> = +0.11(sigma = 0.08), suggesting that the primordial abundances are almost retained for these elements. Strictly, however, they show a slightly increasing trend with a decrease in T_eff (typically on the order of ~10^(-4) dex/K; while this might be due to an improper choice of atmospheric parameters, we found it hard to give a quantitatively reasonable explanation. Regarding Li, we confirmed the well-known T_eff-dependent trend in the Li abundance reported so far (a conspicuous Li-trough at 6300K

We report the discovery of blue-shifted metastable He I* absorption lines at 3188 A and 3889 A with multiple components on high-resolution spectra (R ~ 60,000) of V1280 Scorpii. Similar multiple absorption lines associated with Na I D doublet and Ca II H and K are observed. Na I D doublet absorption lines have been observed since 2009, while the metastable He I* absorption lines were absent in 2009 and were detected in 2011 (four years after the burst). We find different time variations in depths and velocities of blue-shifted absorption components among He I*, Na I, and Ca II. The complex time evolutions of these lines can be explained by assuming changes in density and recombination/ionization rate when the ejecta expand and the photosphere contracts to become hotter. The multiple absorption lines originate in the ejected materials consisting of clumpy components, which obscure a significant part of the continuum emitting region. We estimate the total mass of the ejected material to be on the order of ~ 10^{-4} Mo, using metastable He I* 3188 and 3889 absorption lines., Comment: 8 pages, 8 figures, accepted for publication in PASJ

In memory-constrained algorithms we have read-only access to the input, and the number of additional variables is limited. In this paper we introduce the compressed stack technique, a method that allows to transform algorithms whose space bottleneck is a stack into memory-constrained algorithms. Given an algorithm \alg\ that runs in O(n) time using $\Theta(n)$ variables, we can modify it so that it runs in $O(n^2/s)$ time using a workspace of O(s) variables (for any $s\in o(\log n)$) or $O(n\log n/\log p)$ time using $O(p\log n/\log p)$ variables (for any $2\leq p\leq n$). We also show how the technique can be applied to solve various geometric problems, namely computing the convex hull of a simple polygon, a triangulation of a monotone polygon, the shortest path between two points inside a monotone polygon, 1-dimensional pyramid approximation of a 1-dimensional vector, and the visibility profile of a point inside a simple polygon. Our approach exceeds or matches the best-known results for these problems in constant-workspace models (when they exist), and gives the first trade-off between the size of the workspace and running time. To the best of our knowledge, this is the first general framework for obtaining memory-constrained algorithms.

We present optical ($B$, $V$, $R_{\rm c}$, $I_{\rm c}$ and $y$) and near infrared ($J$, $H$ and $K_{\rm s}$) photometric and spectroscopic observations of a classical nova V1280 Scorpii for five years from 2007 to 2011. Our photometric observations show a declining event in optical bands shortly after the maximum light which continues $\sim$ 250 days. The event is most probably caused by a dust formation. The event is accompanied by a short ($\sim$ 30 days) re-brightening episode ($\sim$ 2.5 mag in $V$), which suggests a re-ignition of the surface nuclear burning. After 2008, the $y$ band observations show a very long plateau at around $y$ = 10.5 for more than 1000 days until April 2011 ($\sim$ 1500 days after the maximum light). The nova had taken a very long time ($\sim$ 50 months) before entering the nebular phase (clear detection of both [\ion{O}{iii}] 4959 and 5007) and is still continuing to generate the wind caused by H-burning. The finding suggests that V1280 Sco is going through the historically slowest evolution. The interval from the maximum light (2007 February 16) to the beginning of the nebular phase is longer than any previously known slow novae: V723 Cas (18 months), RR Pic (10 months), or HR Del (8 months). It suggests that the mass of a white dwarf in the V1280 Sco system might be 0.6 $M_\mathrm{\sun}$ or smaller. The distance, based on our measurements of the expansion velocity combined with the directly measured size of the dust shell, is estimated to be 1.1 $\pm$ 0.5 kpc., Comment: 17 pages, 14 figures, accepted for publication in A&A

We determined chemical abundances of the Extremely Metal-Poor (EMP) star S15-19 ([Fe/H]=-3.0) in the Sextans dwarf galaxy. While heavy neutron-capture elements (e.g., Ba) are generally deficient in EMP stars in dwarf galaxies, this object was shown to have an exceptional over-abundance of Ba ([Ba/Fe] +0.5) by a previous study, which is similar to those of r-process-enhanced stars found in the field halo. Our new high-resolution spectroscopy for this object for the blue region, however, reveals that no clear excess of r-process elements, like Eu, appears in this object. Moreover, a significant excess of carbon ([C/Fe]= +1.0) and a deficiency of Sr ([Sr/Fe] = -1.4) are found for this object. Taking the variation of radial velocities measured at the two different epochs into consideration, the origin of the excesses of heavy neutron-capture elements in S15-19 is not the r-process, but is the s-process in an asymptotic giant branch (AGB) star that was the binary companion (primary) of this object. Carbon- and s-process-enhanced material should have been transferred to the surface of S15-19 across the binary system. These results are compared with carbon-enhanced metal-poor stars in the field halo., Comment: 18 pages, PASJ in press

We present a new data structure called the \emph{Compressed Random Access Memory} (CRAM) that can store a dynamic string $T$ of characters, e.g., representing the memory of a computer, in compressed form while achieving asymptotically almost-optimal bounds (in terms of empirical entropy) on the compression ratio. It allows short substrings of $T$ to be decompressed and retrieved efficiently and, significantly, characters at arbitrary positions of $T$ to be modified quickly during execution \emph{without decompressing the entire string}. This can be regarded as a new type of data compression that can update a compressed file directly. Moreover, at the cost of slightly increasing the time spent per operation, the CRAM can be extended to also support insertions and deletions. Our key observation that the empirical entropy of a string does not change much after a small change to the string, as well as our simple yet efficient method for maintaining an array of variable-length blocks under length modifications, may be useful for many other applications as well.

To revisit the long-standing problem of possible inconsistency concerning the oxygen composition in the current galactic gas and in the solar atmosphere (i.e., the former being appreciably lower by ~0.3 dex) apparently contradicting the galactic chemical evolution, we carried out oxygen abundance determinations for 64 mid- through late-B stars by using the O I 6156-8 lines while taking into account the non-LTE effect, and compared them with the solar O abundance established in the same manner. The resulting mean oxygen abundance was = 8.71 (+/- 0.06), which means that [O/H] (star-Sun differential abundance) is ~-0.1, the difference being less significant than previously thought. Moreover, since the 3D correction may further reduce the reference solar oxygen abundance (8.81) by ~0.1 dex, we conclude that the photospheric O abundances of these B stars are almost the same as that of the Sun. We also determined the non-LTE abundances of neon for the sample B stars from Ne I 6143/6163 lines to be = 8.02 (+/- 0.09), leading to the Ne-to-O ratio of ~0.2 consistent with the recent studies. This excludes a possibility of considerably high Ne/O ratio once proposed as a solution to the confronted solar model problem., Comment: 11 pages, 7 figures, 2 tables, accepted for publication in PASJ, Vol.62, No.5 (2010)

We present optical and near-infrared (NIR) photometry of a classical nova, V2362 Cyg (= Nova Cygni 2006). V2362 Cyg experienced a peculiar rebrightening with a long duration from 100 to 240 d after the maximum of the nova. Our multicolor observation indicates an emergence of a pseudophotosphere with an effective temperature of 9000 K at the rebrightening maximum. After the rebrightening maximum, the object showed a slow fading homogeneously in all of the used bands for one week. This implies that the fading just after the rebrightening maximum ( less or equal 1 week ) was caused by a slowly shrinking pseudophotosphere. Then, the NIR flux drastically increased, while the optical flux steeply declined. The optical and NIR flux was consistent with blackbody radiation with a temperature of 1500 K during this NIR rising phase. These facts are likely to be explained by dust formation in the nova ejecta. Assuming an optically thin case, we estimate the dust mass of 10^(-8) -- 10^(-10) M_solar, which is less than those in typical dust-forming novae. These results support the senario that a second, long-lasting outflow, which caused the rebrightening, interacted with a fraction of the initial outflow and formed dust grains., Comment: 6 pages, 4 figures, 2010, PASJ, 62, 1103--1108, in press

For the first time we show the detailed late-stage chemical evolution history of small nearby dwarf spheroidal galaxy in the Local Group. We present the results of a high resolution (R$\sim$20000) FLAMES/GIRAFFE abundance study at ESO/VLT of 81 photometrically selected red giant branch stars in the central 25$'$ of the Fornax dwarf spheroidal galaxy. We present abundances of \alfe\ (Mg, Si, Ca and Ti), iron-peak elements (Fe, Ni and Cr) and heavy elements (Y, Ba, La, Nd and Eu). Our sample was randomly selected, and is clearly dominated by the younger and more metal rich component of Fornax which represents the major fraction of stars in the central region. This means that the majority of our stars are 1$-$4 Gyr old, and thus represent the end phase of chemical evolution in this system. Our sample of stars has unusually low [$\alpha$/Fe], [Ni/Fe] and [Na/Fe] compared to the Milky Way stellar populations at the same [Fe/H]. The particularly important role of stellar winds from low metallicity AGB stars in the creation of s-process elements is clearly seen from the high [Ba/Y]. Furthermore, we present evidence for an s-process contribution to Eu., Comment: 40 pages, 20 figures, accepted for publication in A&A

Grammar based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular compression schemes. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let $S$ be a string of length $N$ compressed into a context-free grammar $\mathcal{S}$ of size $n$. We present two representations of $\mathcal{S}$ achieving $O(\log N)$ random access time, and either $O(n\cdot \alpha_k(n))$ construction time and space on the pointer machine model, or $O(n)$ construction time and space on the RAM. Here, $\alpha_k(n)$ is the inverse of the $k^{th}$ row of Ackermann's function. Our representations also efficiently support decompression of any substring in $S$: we can decompress any substring of length $m$ in the same complexity as a single random access query and additional $O(m)$ time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern $P$ with at most $k$ errors in time $O(n(\min\{|P|k, k^4 + |P|\} + \log N) + occ)$, where $occ$ is the number of occurrences of $P$ in $S$. Finally, we generalize our results to navigation and other operations on grammar-compressed ordered trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two "biased" weighted ancestor data structures, and a compact representation of heavy paths in grammars., Comment: Preliminary version in SODA 2011

(Abridged) OJ287 is a BL Lac object that has shown double-peaked bursts at regular intervals of ~12 yr during the last ~40 yr. We analyse optical photopolarimetric monitoring data from 2005-2009, during which the latest double-peaked outburst occurred. The aim of this study is twofold: firstly, we aim to analyse variability patterns and statistical properties of the optical polarization light-curve. We find a strong preferred position angle in optical polarization. The preferred position angle can be explained by separating the jet emission into two components: an optical polarization core and chaotic jet emission. The optical polarization core is stable on time scales of years and can be explained as emission from an underlying quiescent jet component. The chaotic jet emission sometimes exhibits a circular movement in the Stokes plane. We interpret these events as a shock front moving forwards and backwards in the jet, swiping through a helical magnetic field. Secondly, we use our data to assess different binary black hole models proposed to explain the regularly appearing double-peaked bursts in OJ287. We compose a list of requirements a model has to fulfil. The list includes not only characteristics of the light-curve but also other properties of OJ287, such as the black hole mass and restrictions on accretion flow properties. We rate all existing models using this list and conclude that none of the models is able to explain all observations. We discuss possible new explanations and propose a new approach to understanding OJ287. We suggest that both the double-peaked bursts and the evolution of the optical polarization position angle could be explained as a sign of resonant accretion of magnetic field lines, a 'magnetic breathing' of the disc., Comment: Accepted for publication in MNRAS (26 pages, 24 figures, 4 tables)