Bit-parallel -matching and suffix automata

(δ,γ)-matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P_1…m and a text T_1…n on an alphabet of integers, find the occurrences P^′ of the pattern in the text such that (i) , and (ii) . The problem makes sense for δγδm. Several techniques for (δ,γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mnlog(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mnlog(δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.     

String matching in quantum time

We show how to determine whether a given pattern p of length m occurs in a given text t of length n in time (where allows for logarithmic factors in m and n/m) with inverse polynomial failure probability. This algorithm combines quantum searching algorithms with a technique from parallel string matching, called Deterministic Sampling.     

Maximum induced matching problem on hhd-free graphs

We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m²) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m³). Then, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results.     

Efficient exponential-time algorithms for edit distance between unordered trees

The edit distance problem for rooted unordered trees is known to be NP-hard. Based on this fact, this paper studies exponential-time algorithms for the problem. For a general case, an $O(\min ({1.26}^{n_1+n_2},2^{b_1+b_2}\cdot \text{<mi mathvariant="italic" is="true">poly</mi>}(n_1,n_2)))$ time algorithm is presented, where $n_1$ and $n_2$ are the numbers of nodes and $b_1$ and $b_2$ are the numbers of branching nodes in two input trees. This algorithm is obtained by a combination of dynamic programming, exhaustive search, and maximum weighted bipartite matching. For bounded degree trees over a fixed alphabet, it is shown that the problem can be solved in $O({(1+ϵ)}^{n_1+n_2})$ time for any fixed $ϵ>0$. This result is achieved by avoiding duplicate calculations for identical subsets of small subtrees.     

Two-person repeated games with finite automata

We study two-person repeated games in which a player with a restricted set of strategies plays against an unrestricted player. An exogenously given bound on the complexity of strategies, which is measured by the size of the smallest automata that implement them, gives rise to a restriction on strategies available to a player.  We examine the asymptotic behavior of the set of equilibrium payoffs as the bound on the strategic complexity of the restricted player tends to infinity, but sufficiently slowly. Results from the study of zero sum case provide the individually rational payoff levels. Received February 1997/revised version March 2000     

Optimal portfolio and consumption selection with default risk

We investigate an optimal portfolio and consumption choice problem with a defaultable security. Under the goal of maximizing the expected discounted utility of the average past consumption, a dynamic programming principle is applied to derive a pair of second-order parabolic Hamilton-Jacobi-Bellman (HJB) equations with gradient constraints. We explore these HJB equations by a viscosity solution approach and characterize the post-default and pre-default value functions as a unique pair of constrained viscosity solutions to the HJB equations.     

Pricing vulnerable European options with stochastic default barriers

CF Lo and KC Ku Institute of Theoretical Physics and Department of Physics, The Chinese University of Hong Kong, Shatin, Hong Kong, China Email: cho-hoi_hui{at}hkma.gov.hk Received on 31 July 2006. Accepted on 15 March 2007. This paper develops a valuation model of European options incorporatinga stochastic default barrier, which extends a constant defaultbarrier proposed in the Hull–White model. The defaultbarrier is considered as an option writer's liability. Closed-formsolutions of vulnerable European option values based on themodel are derived to study the impact of the stochastic defaultbarriers on option values. The numerical results show that negativecorrelation between the firm values and the stochastic defaultbarriers of option writers gives material reductions in optionvalues where the options are written by firms with leverageratios corresponding to BBB or BB ratings.     

Enhancing credit default swap valuation with meshfree methods

In this paper, we apply the meshfree radial basis function (RBF) interpolation to numerically approximate zero-coupon bond prices and survival probabilities in order to price credit default swap (CDS) contracts. We assume that the interest rate follows a Cox-Ingersoll-Ross process while the default intensity is described by the Exponential-Vasicek model. Several numerical experiments are conducted to evaluate the approximations by the RBF interpolation for one- and two-factor models. The results are compared with those estimated by the finite difference method (FDM). We find that the RBF interpolation achieves more accurate and computationally efficient results than the FDM. Our results also suggest that the correlation between factors does not have a significant impact on CDS spreads.     

Optimal consumption and investment with insurer default risk

We solve the optimal consumption and investment problem in an incomplete market, where borrowing constraints and insurer default risk are considered jointly. We derive in closed-form the optimal consumption and investment strategies. We find two main results by quantitative analysis. As insurer default risk increases, the proportion of wealth invested in stocks could increase when wealth is small, and decrease when wealth is large. As risk aversion increases, the voluntary annuity demand could increase when insurer default risk is low, and decrease when this risk is high.     

An inventory system with two suppliers and default risk

This paper considers the problem of joint replenishment and pricing for a single product with two suppliers and supply disruption. Our objective is to maximize the total profit by choosing an appropriate replenishment and pricing policy. We not only obtain that the form of the optimal policy has a (s,S,p,σ,Σ)-type, but also analyze how supply disruption affects the profit function and the optimal policy.     

Robust non-zero-sum investment and reinsurance game with default risk

This paper investigates a non-zero-sum stochastic differential game between two competitive CARA insurers, who are concerned about the potential model ambiguity and aim to seek the robust optimal reinsurance and investment strategies. The ambiguity-averse insurers are allowed to purchase reinsurance treaty to mitigate individual claim risks; and can invest in a financial market consisting of one risk-free asset, one risky asset and one defaultable corporate bond. The objective of each insurer is to maximize the expected exponential utility of his terminal surplus relative to that of his competitor under the worst-case scenario of the alternative measures. Applying the techniques of stochastic dynamic programming, we derive the robust Nash equilibrium reinsurance and investment policies explicitly and present the corresponding verification theorem. Finally, we perform some numerical examples to illustrate the influence of model parameters on the equilibrium reinsurance and investment strategies and draw some economic interpretations from these results.     

Reversible cellular automata with memory of delay type

The effect of delay type memory of past states on reversible elementary cellular automata (CA) is examined in this study. It is assessed in simple scenarios, such as elementary CA, but the feasibility of enriching the dynamics with memory in a general reversible CA context is also outlined. © 2014 Wiley Periodicals, Inc. Complexity 20: 49–56, 2014     

Optimal reinsurance with regulatory initial capital and default risk

In a reinsurance contract, a reinsurer promises to pay the part of the loss faced by an insurer in exchange for receiving a reinsurance premium from the insurer. However, the reinsurer may fail to pay the promised amount when the promised amount exceeds the reinsurer’s solvency. As a seller of a reinsurance contract, the initial capital or reserve of a reinsurer should meet some regulatory requirements. We assume that the initial capital or reserve of a reinsurer is regulated by the value-at-risk (VaR) of its promised indemnity. When the promised indemnity exceeds the total of the reinsurer’s initial capital and the reinsurance premium, the reinsurer may fail to pay the promised amount or default may occur. In the presence of the regulatory initial capital and the counterparty default risk, we investigate optimal reinsurance designs from an insurer’s point of view and derive optimal reinsurance strategies that maximize the expected utility of an insurer’s terminal wealth or minimize the VaR of an insurer’s total retained risk. It turns out that optimal reinsurance strategies in the presence of the regulatory initial capital and the counterparty default risk are different both from optimal reinsurance strategies in the absence of the counterparty default risk and from optimal reinsurance strategies in the presence of the counterparty default risk but without the regulatory initial capital.     

Parameterized matching with mismatches

The problem of approximate parameterized string searching consists of finding, for a given text t=t₁t₂…t_n and pattern p=p₁p₂…p_m over respective alphabets Σ_t and Σ_p, the injection π_i from Σ_p to Σ_t maximizing the number of matches between π_i(p) and t_it_i+1…t_i+m−1 (i=1,2,…,n−m+1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n+(r_p×r_t)α(r_t)log(r_t)), where r_p and r_t denote the number of runs in the corresponding encodings for y and x, respectively, and α is the inverse of the Ackermann's function.     

Asset proportions in optimal portfolios with dependent default risks

In this note, we consider the dependent default risk model of factor type. The dependence between the returns of assets is driven by default indicators. Sufficient conditions on the dependence structure of default indicators and on the utility function are investigated which enable one to order the optimal amount invested in each asset. We thus complement one result in [Cheung, K.C., Yang, H., 2004. Ordering optimal proportions in the asset allocation problem with dependent default risks. Insurance: Math. Econom. 35, 595-609].     

Fast parameterized matching with q-grams

Two strings parameterize match if there is a bijection defined on the alphabet that transforms the first string character by character into the second string. The problem of finding all parameterized matches of a pattern in a text has been studied in both one and two dimensions but the research has been centered on developing algorithms with good worst-case performance. We present algorithms that solve this problem in sublinear time on average for moderately repetitive patterns.     

Pricing VXX option with default risk and positive volatility skew

This paper proposes and makes a comparative study of alternative models for VXX option pricing. Factors such as mean-reversion, jumps, default risk and positive volatility skew are taken into consideration. In particular, default risk is characterized by jump-to-default framework and the “positive volatility skew” issue is addressed by stochastic volatility of volatility and jumps. Daily calibration is conducted and comparative study of the models is performed to check whether they properly fit market prices and generate reasonable positive volatility skews and deltas. Overall, jump-to-default extended LRJ model with positive correlated stochastic volatility (called JDLRJSV in the paper) serves as the best model in all the required aspects.