Finding approximate patterns in strings

Let p (the pattern) be a string and t ≥ 0 an integer. The problem of locating in any string a substring whose edit distance from p is at most a given constant t is considered. An algorithm is presented to construct a deterministic finite-state automaton that solves the problem.     

Evolving technical trading rules for spot foreign-exchange markets using grammatical evolution

Grammatical Evolution (GE) is a novel, data-driven, model-induction tool, inspired by the biological gene-to-protein mapping process. This study provides an introduction to GE, and applies the methodology in an attempt to uncover useful technical trading rules which can be used to trade foreign exchange markets. In this study, each of the evolved rules (programs) represents a market trading system. The form of these programs is not specified ex-ante, but emerges by means of an evolutionary process. Daily US-DM, US-Stg and US-Yen exchange rates for the period 1992 to 1997 are used to train and test the model. The findings suggest that the developed rules earn positive returns in hold-out sample test periods, after allowing for trading and slippage costs. This suggests potential for future research to determine whether further refinement of the methodology adopted in this study could improve the returns earned by the developed rules. It is also noted that this novel methodology has general utility for rule-induction, and data mining applications.MSC codes: 91B84, 68W10, 62J02     

Finding blocks and other patterns in a random coloring of ℤ

Let ξ = (ξ_k)_k∈? be i.i.d. with P(ξ_k = 0) = P(ξ_k = 1) = 1/2, and let S: = (S_k) be a symmetric random walk with holding on ?, independent of ξ. We consider the scenery ξ observed along the random walk path S, namely, the process (χ_k := ξ). With high probability, we reconstruct the color and the length of blockⁿ, a block in ξ of length ≥ n close to the origin, given only the observations (χ_k). We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on blockⁿ and in the interval [?3ⁿ,3ⁿ]. Moreover, we reconstruct with high probability a piece of ξ of length of the order 3 around blockⁿ, given only 3 observations collected by the random walker starting on the boundary of blockⁿ. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Jamming in attractive granular media

The jamming transition is studied numerically in systems of particles with attraction. Unlike the purely repulsive case where a single transition separates the jammed from unjammed phase, the presence of even an infinitesimal amount of attraction yields two distinct transitions: connectivity and rigidity percolation. We measure critical exponents of these two percolation transitions and find that they are different than the corresponding lattice values. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Data-driven estimation of diurnal patterns of durations between trades on financial markets

We propose a data-driven local linear estimator for diurnal patterns of transaction durations with a brief discussion on its asymptotics. The standardized durations are modeled by the EACD. Codes in R are developed for practical implementation. Application is illustrated by data examples.     

Finding Scores in Tournaments

A tournamentT_nis an orientation of the complete graph onnvertices. We continue the algorithmic study initiated by10of recognizing various directed trees in tournaments. Hell and Rosenfeld studied the complexity of finding various oriented paths in tournaments by probing edge directions. Here, we investigate the complexity of finding a vertex of prescribed outdegree (or indegree) in the same model. We show that the complexity of finding a vertex of outdegreek( ≤ (n − 1)/2) inT_nis Θ(nk). This bound is in sharp contrast to the Θ(n) bound for selection in the case of transitive tournaments. We also establish tight bounds for finding vertices of prescribed degree from the adjacency matrix of general directed/undirected graphs. These bounds generalize the classical bound of11for finding a sink (a vertex of outdegree 0 and indegreen − 1) in a directed graph.     

Finding hypernetworks in directed hypergraphs

The term “hypernetwork” (more precisely, s-hypernetwork and (s, d)-hypernetwork) has been recently adopted to denote some logical structures contained in a directed hypergraph. A hypernetwork identifies the core of a hypergraph model, obtained by filtering off redundant components. Therefore, finding hypernetworks has a notable relevance both from a theoretical and from a computational point of view.     

Informational inefficiency in financial markets

The existence of an informational inefficiency in the equity market is identified by analysing information publicly available on the internet. A large volume of blog data is used for this purpose. Informational inefficiency is established by converting company-specific blog sentiment data into a trading strategy and analysing its performance. An information-based model that approximately replicates the strategy is developed to estimate the degree of information disparity. The result shows that an efficient internet search engine can considerably enhance market efficiency, as measured in terms of the information flow rate.     

Chaotic dynamics in agricultural markets

In a recent article, Chiarella [7] used a nonlinear supply curve with exactly one inflection point in the context of a cobweb model in order to make plausible that chaotic behaviour may result in such a model. There is, however, no exact proof under what conditions chaos can actually show up since Chiarella confines the analysis to a second order approximation to his difference equation. In a somewhat different model (a linear supply and a nonlinear demand curve which can be given a microeconomic foundation) we show that, under the formation of adaptive price expectations, the resulting adjustment mechanism can generate a wide range of dynamic behaviour (depending on the prevailing parameter constellations) such as stability, bifurcations with stable cycles of period 2, 4, 8, ... and, finally, aperiodic time paths, (i.e. we can show that period-3 cycles exist). In a second step, long historical time series of weekly price observations in German agricultural markets are scrutinized with regard to the hypothesis of nonlinearities. We study their correlation dimensions only recently employed by economists as a characteristic measure which allows, under certain conditions, to distinguish between deterministic chaos and random noise. Our results do not provide evidence to reject the hypothesis, although noise infection of the series cannot be ruled out.     

Markovian networks in labour markets

In labour theory, equilibrium is described in terms of mean variables, which is limited and can be misleading. In this article, we model the labour market as a closed Markovian network and find the steady state distribution of unemployment and advertised vacancies. We determine the stochastic equilibrium distribution for two different types of matching functions and allow for both unemployed and on the job search. In general cases, where probabilities cannot be analytically computed, we find restrictions that must hold for all matching processes. Our modelling is applicable to most economic markets with frictions.     

Portfolio optimization in stochastic markets

We consider a multiperiod mean-variance model where the model parameters change according to a stochastic market. The mean vector and covariance matrix of the random returns of risky assets all depend on the state of the market during any period where the market process is assumed to follow a Markov chain. Dynamic programming is used to solve an auxiliary problem which, in turn, gives the efficient frontier of the mean-variance formulation. An explicit expression is obtained for the efficient frontier and an illustrative example is given to demonstrate the application of the procedure.     

Curve following in illiquid markets

In this article the problem of curve following in an illiquid market is addressed. The optimal control is characterised in terms of the solution to a coupled FBSDE involving jumps via the technique of the stochastic maximum principle. Analysing this FBSDE, we further show that there are buy and sell regions. In the case of quadratic penalty functions the FBSDE admits an explicit solution which is determined via the four step scheme. The dependence of the optimal control on the target curve is studied in detail.     

Complexity models in financial markets

In this approach, the complexity of the self-organizing microstructure of the stock exchange is explicitly taken into consideration: the process of offers and trades as well as the adjustment of individual expectations are modelled with help of a (stochastic) jump process. Its abilities are illustrated by modelling the continuous quotations of asset prices at an auction type stock exchange. The functional form of the transition (hazard) rates is chosen to reflect the individual preferences and expectations as well as the economic environment. The model is described in detail and examples of Monte Carlo simulation results are presented.     

Option pricing in incomplete markets

Expected utility maximization is a very useful approach for pricing options in an incomplete market. The results from this approach contain many important features observed by practitioners. However, under this approach, the option prices are determined by a set of coupled nonlinear partial differential equations in high dimensions. Thus, it represents numerous significant difficulties in both theoretical analysis and numerical computations. In this paper, we present accurate approximate solutions for this set of equations.     

Finding stabbing lines in 3-space

A line intersecting all polyhedra in a setℬ is called a “stabber” for the setℬ. This paper addresses some combinatorial and algorithmic questions about the setℒ(ℬ) of all lines stabbingℬ. We prove that the combinatorial complexity ofℒ(ℬ) has an upper bound, wheren is the total number of facets inℬ, andc is a suitable constant. This bound is almost tight. Within the same time bound it is possible to determine if a stabbing line exists and to find one. The research of M. Pellegrini was partially supported by Eni and Enidata within the AXL project, and by NSF Grant CCR-8901484. A preliminary version appeared in theProceedings of the Second ACM-SIAM Symposium on Discrete Algorithms, pp. 24–31.     

Finding Optimal Routings in Hamming Graphs

A routing R in a graph consists of a simple path p_uvfromu to v for each ordered pair of distinct vertices (u, v). We will call R optimal if all the paths p_uvare shortest paths and if edges of the graph occur equally often in the paths of R. In 1994, Solé gave a sufficient condition involving the automorphism group for a graph to have an optimal routing in this sense. Graphs which satisfy Solé’s condition are called orbital regular graphs. It is often difficult to determine whether or not a given graph is orbital regular. In this paper, we give a necessary and sufficient condition for a Hamming graph to be orbital regular with respect to a certain natural subgroup of automorphisms.     

Finding Adam in random growing trees

We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least , the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε. In the uniform attachment case we show that the optimal K is subpolynomial in , and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in . We conclude the paper with several open problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 158–172, 2017     

Finding Hamiltonian circuits in quasi-adjoint graphs

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothermic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718–729]. This paper presents a class of digraphs: the quasi-adjoint graphs. This class includes the ones used in the paper cited above. A polynomial recognition algorithm in O(n³), as well as a polynomial algorithm in O(n²+m²) for finding a Hamiltonian circuit in these graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a path with three vertices) are discussed.     

Finding disjoint surfaces in 3-manifolds

Let M be a compact connected orientable 3-manifold, with non-empty boundary that contains no two-spheres. We investigate the existence of two properly embedded disjoint surfaces $S_{1}$ and $S_{2}$ such that $M - (S_{1} \cup S_{2})$ is connected. We show that there exist two such surfaces if and only if M is neither a $\mathbb Z _{2}$ homology solid torus nor a $\mathbb Z _{2}$ homology cobordism between two tori. In particular, the exterior of a link with at least three components always contains two such surfaces. The proof mainly uses techniques from the theory of groups, both discrete and profinite.     

Finding a Sun in Building-Free Graphs

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (Hoàng in SIAM J Discret Math 23:2156–2162, 2010). We show that whether a building-free graph contains a sun can be decided in O(min{mn ³, m ^1.5 n ²}) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.