Consider a regular expression r of length m and a text string T of length n over an alphabet Σ. Then, the RE shortest substring search problem is to find all shortest substrings of T matching r. The ...previous algorithm proposed by Clarke and Cormack uses an ε-free nondeterministic finite automaton (NFA) and runs in O(ksn) time and O(s) space, where k is the maximum number of outgoing transitions for any state and symbol, and s is the number of states. Generally, an ε-free NFA obtained from a regular expression has s=O(m) and k=O(m); thus the algorithm takes O(m2n) time and O(m) space. We propose a faster algorithm that runs in O(mn) time and O(m) space. The proposed algorithm is based on a Thompson automaton which is an NFA with ε-transitions.
•An RE shortest substring search problem for regular expressions is considered.•A faster algorithm for the RE shortest search problem is proposed.•The proposed algorithm is designed based on a Thompson automaton.
Abstract
Microquasar SS 433 located at the geometric center of radio nebula W 50 is a suitable source for investigating the physical process of how galactic jets affect the surrounding interstellar ...medium (ISM). Previous studies have searched for evidence of the interaction between the SS 433 jet and ISM, such as neutral hydrogen gas and molecular clouds; however, it is still unclear which ISM interacts with the jet. We looked for new molecular clouds that possibly interact at the terminal of the SS 433 eastern jet using the Nobeyama 45 m telescope and the Atacama Submillimeter Telescope Experiment (ASTE). We identified two molecular clouds, comprising many small clumps, in the velocity range of 30.1–36.5 km s−1 for the first time. These clouds have complex velocity structures, and one of them has a density gradient toward SS 433. Although it is difficult to conclude the relation between the molecular clouds and the SS 433/W 50 system, there is a possibility that the eastern structure of W 50 constructed by the SS 433 jet swept up tiny molecular clumps drifting in the surroundings and formed the molecular clouds that we identified in this study.
The spread of wearable watch devices with photoplethysmography (PPG) sensors has made it possible to use continuous pulse wave data during daily life. We examined if PPG pulse wave data can be used ...to detect sleep apnea, a common but underdiagnosed health problem associated with impaired quality of life and increased cardiovascular risk. In 41 patients undergoing diagnostic polysomnography (PSG) for sleep apnea, PPG was recorded simultaneously with a wearable watch device. The pulse interval data were analyzed by an automated algorithm called auto-correlated wave detection with adaptive threshold (ACAT) which was developed for electrocardiogram (ECG) to detect the cyclic variation of heart rate (CVHR), a characteristic heart rate pattern accompanying sleep apnea episodes. The median (IQR) apnea-hypopnea index (AHI) was 17.2 (4.4-28.4) and 22 (54%) subjects had AHI ≥15. The hourly frequency of CVHR (Fcv) detected by the ACAT algorithm closely correlated with AHI (r = 0.81), while none of the time-domain, frequency-domain, or non-linear indices of pulse interval variability showed significant correlation. The Fcv was greater in subjects with AHI ≥15 (19.6 ± 12.3 /h) than in those with AHI <15 (6.4 ± 4.6 /h), and was able to discriminate them with 82% sensitivity, 89% specificity, and 85% accuracy. The classification performance was comparable to that obtained when the ACAT algorithm was applied to ECG R-R intervals during the PSG. The analysis of wearable watch PPG by the ACAT algorithm could be used for the quantitative screening of sleep apnea.
In Variant 4 of the one-way trading game El-Yaniv, Fiat, Karp, and Turpin, 2001, a player has one dollar at the beginning and wants to convert it to yen only by one-way conversion. The exchange rate ...is guaranteed to fluctuate between m and M, and only the maximum fluctuation ratio φ = M/m is informed to the player in advance. The performance of an algorithm for this game is measured by the competitive ratio. El-Yaniv et al. derived the best possible competitive ratio over all algorithms for this game. However, it seems that the behavior of the best possible algorithm itself has not been explicitly described. In this paper we reveal the behavior of the best possible algorithm by solving a linear optimization problem. The behavior turns out to be quite different from that of the best possible algorithm for Variant 2 in which the player knows m and M in advance.
The bin packing problem is a problem of finding an assignment of a sequence of items to a minimum number of bins, each of capacity one. An online algorithm for the bin packing problem is an algorithm ...that irrevocably assigns each item one by one from the head of the sequence. Gutin, Jensen, and Yeo (2006) considered a version in which all items are only of two different sizes and the online algorithm knows the two possible sizes in advance, and gave an optimal online algorithm for the case when the larger size exceeds 1/2. In this paper we provide an optimal online algorithm for some of the cases when the larger size is at most 1/2, on the basis of a framework that facilitates the design and analysis of algorithms.
The gut bacterium Gordonibacter urolithinfaciens DSM 27213 metabolizes ellagic acid into three polyphenol compounds, namely, urolithin M5, urolithin M6, and urolithin C, which are collectively called ...urolithin. The key reactions of this metabolic pathway are the dehydroxylation of the phenolic hydroxy group, i.e., conversion of urolithin M5 to urolithin M6, and successive conversion of urolithin M6 to urolithin C. By testing the effects of various electron-transferring compounds on the dehydroxylation reactions, methylviologen was found to effectively support the dehydroxylation catalyzed by the cell free extracts. The urolithin dehydroxylating enzymes were found in the soluble fraction of the cell free extracts. The urolithin dehydroxylation was found to be coupled with reduction of dicationic methylviologen to a cation radical form catalyzed by enzymes with hydrogen as an electron donor, which was also found with the soluble fraction. Further investigation of the reaction in the presence of natural cofactors with or without methylviologen and hydrogen revealed the involvement of NADPH and FAD in the electron transportation systems of the urolithin dehydroxylation.
This paper presents a new method to translate a regular expression into a nondeterministic finite automaton (an NFA for short). Let r be a regular expression and let M be a Thompson automaton for r. ...We first introduce a labeled Thompson automaton defined by assigning two types of expressions which denote prefixes and suffixes of words in L(r) to each state of M. Then we give new ϵ-free NFAs constructed from a labeled Thompson automaton. These NFAs are called a prefix equation automaton and a suffix equation automaton. We show that a suffix equation automaton is isomorphic to an equation automaton defined by Antimirov. Furthermore we give an NFA called a unified equation automaton by joining two NFAs. Thus the number of states of a unified equation automaton can be smaller than that of an equation automaton.
Let us consider a regular expression r of length m and a text string T of length n over an alphabet Σ. Then, the RE minimal substring search problem is to find all minimal substrings of T matching r. ...Yamamoto proposed O(mn) time and O(m) space algorithm using a Thompson automaton. In this paper, we improve Yamamoto's algorithm by introducing parallelism. The proposed algorithm runs in O(mn) time in the worst case and in O(mn/p) time in the best case, where p denotes the number of processors. Besides, we show a parameter related to the parallel time of the proposed algorithm. We evaluate the algorithm experimentally.
Abstract
We carried out new CO (J = 1–0, 2–1, and 3–2) observations with NANTEN2 and ASTE in the region of the twin Galactic mini-starbursts NGC 6334 and NGC 6357. We detected two velocity molecular ...components of 12 km s−1 velocity separation, which is continuous over 3° along the plane. In NGC 6334 the two components show similar two-peaked intensity distributions toward the young H ii regions and are linked by a bridge feature. In NGC 6357 we found spatially complementary distribution between the two velocity components as well as a bridge feature in velocity. Based on these results we hypothesize that the two clouds in the two regions collided with each other in the past few Myr and triggered the formation of the starbursts over ∼ 100 pc. We suggest that the formation of the starbursts happened toward the collisional region of extent ∼ 10 pc with initial high molecular column densities. For NGC 6334 we present a scenario which includes spatial variation of the colliding epoch due to non-uniform cloud separation. The scenario possibly explains the apparent age differences among the young O stars in NGC 6334, which range from 104 yr to 106 yr; the latest collision happened within 105 yr toward the youngest stars in NGC 6334 I(N) and I which exhibit molecular outflows without H ii regions. For NGC 6357 the O stars were formed a few Myr ago, and the cloud dispersal by the O stars is significant. We conclude that cloud–cloud collision offers a possible explanation of the mini-starburst over a 100 pc scale.
A searchable symmetric encryption (SSE) scheme is a method that searches encrypted data without decrypting it. In this paper, we address the substring search problem such that for a set D of ...documents and a pattern p, we find all occurrences of p in D. Here, a document and a pattern are defined as a string. A directed acyclic word graph (DAWG), which is a deterministic finite automaton, is known for solving a substring search problem on a plaintext. We improve a DAWG so that all transitions of a DAWG have distinct symbols. Besides, we present a space-efficient and secure substring SSE scheme using an improved DAWG. The proposed substring SSE scheme consists of an index with a simple structure, and the size is O(n) for the total size n of documents.
PDF
