Construction of the value function in a pursuit-evasion game with three pursuers and one evader

A differential pursuit-evasion game is considered with three pursuers and one evader. It is assumed that all objects (players) have simple motions and that the game takes place in a plane. The control vectors satisfy geometrical constraints and the evader has a superiority in control resources. The game time is fixed. The value functional is the distance between the evader and the nearest pursuer at the end of the game. The problem of determining the value function of the game for any possible position is solved.

Three possible cases for the relative arrangement of the players at an arbitrary time are studied: “one-after-one”, “two-after-one”, “three-after-one-in-the-middle” and “three-after-one”. For each of the relative arrangements of the players a guaranteed result function is constructed. In the first three cases the function is expressed analytically. In the fourth case a piecewise-programmed construction is presented with one switchover, on the basis of which the value of the function is determined numerically. The guaranteed result function is shown to be identical with the game value function. When the initial pursuer positions are fixed in an arbitrary manner there are four game domains depending on their relative positions. The boundary between the “three-after-one-in-the-middle” domain and the “three-after-one” domain is found numerically, and the remaining boundaries are interior Nicomedean conchoids, lines and circles. Programs are written that construct singular manifolds and the value function level lines.     

Periodicity and repetitions in parameterized strings

One of the most beautiful and useful notions in the Mathematical Theory of Strings is that of a Period, i.e., an initial piece of a given string that can generate that string by repeating itself at regular intervals. Periods have an elegant mathematical structure and a wealth of applications [F. Mignosi and A. Restivo, Periodicity, Algebraic Combinatorics on Words, in: M. Lothaire (Ed.), Cambridge University Press, Cambridge, pp. 237–274, 2002]. At the hearth of their theory, there are two Periodicity Lemmas: one due to Lyndon and Schutzenberger [The equation a^M=b^Nc^P in a free group, Michigan Math. J. 9 (1962) 289–298], referred to as the Weak Version, and the other due to Fine and Wilf [Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965) 109–114]. In this paper, we investigate the notion of periodicity and the closely related one of repetition in connection with parameterized strings as introduced by Baker [Parameterized pattern matching: algorithms and applications, J. Comput. System Sci. 52(1) (1996) 28–42; Parameterized duplication in strings: algorithms and an application to software maintenance, SIAM J. Comput. 26(5) (1997) 1343–1362]. In such strings, the notion of pairwise match or “equivalence” of symbols is more relaxed than the usual one, in that it rests on some mapping, rather than identity, of symbols. It seems natural to try and extend notions of periods and periodicities to encompass parameterized strings. However, we know of no previous attempt in this direction. Our preliminary investigation yields results as follows. For periodicity, we get (a) a generalization of the Weak Version of the Periodicity Lemma for parameterized strings, showing that it is essential that the two mappings inducing the periodicity must commute; (b) a proof that an analogous of the Lemma by Fine and Wilf [Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965) 109–114] cannot hold for parameterized strings, even if the mappings inducing the periodicity “commute”, in a sense to be specified below; (c) a proof that parameterized strings over an alphabet of at least three letters may have a set of periods which differ from those of any binary string of the same length—whereby the parameterized analog of a classic result by Guibas and Odlyzko [String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30 (1981) 183–208] cannot hold. We also derive necessary and sufficient conditions characterizing parameterized repetitions, which are patterns of length at least twice that of the period, and show how the notion of root differs from the standard case, and highlight some of the implications on extending algorithmic criteria previously adopted for string searching, detection of repetitions and the likes. Finally, as a corollary of our main results, we also show that binary parameterized strings behave much in the same way as non-parameterized ones with respect to periodicity and repetitions, while there is a substantial difference for strings over alphabets of at least three symbols.     

Note on integer-valued bilinear time series models

This note reconsiders the nonnegative integer-valued bilinear processes introduced by Doukhan et al. [Doukhan, P., Latour, A., Oraichi, D., 2006. A simple integer-valued bilinear time series model. Adv. Appl. Prob. 38, 559–578]. Using a hidden Markov argument, we extend their result of the existence of a stationary solution for the INBL(1, 0, 1, 1) process to the class of superdiagonal models. Our approach also yields improved parameter restrictions for several moment conditions compared to the ones in [Doukhan, P., Latour, A., Oraichi, D., 2006. A simple integer-valued bilinear time series model. Adv. Appl. Prob. 38, 559–578].     

A natural prior probability distribution derived from the propositional calculus

A σ-additive probability measure on the real interval [0, 1] is defined by considering the expected values of “randomly chosen” large formulae of the propositional calculus, where the propositional variables are treated as independent random variables on {0, 1} with expected value . Although arising naturally from logical and/or cognitive considerations, this measure is extremely complex and displays certain formally pathological features, including infinite density at all points of a certain dense subset of [0, 1]. Certain variantsof the construction are also considered. The introduction includes an account of motivation for the study of such measures arising from a fundamental problem in inexact reasoning.     

On generalized formulation of the equilibrium problem of an elastic strip

A “nonenergetic” formulation of the boundary value problems of statics of an elastic strip based on the principle of admissible displacements, is studied. The formulation makes possible, in particular, the study of problems concerning the strips of infinite energy, while retaining the external form of the “energetic” formulation /1–3/, and produces unique solvability of the problem under weaker restrictions imposed on the external loads. Such a formulation is also possible for other problems of the theory of elasticity.     

Right-hand solutions of the differential equations of dynamics for mechanical systems with sliding friction

As a further development of Painlevé's theory [1], the existence, continuability and uniqueness of righ-hand solutions of the differential equations of dynamics, and, under certain additional conditions, of the equations of motion of holonomic mechanical systems with sliding friction [2] are considered. In classical mechanics, acceleration is essentially defined as the right-hand derivative of velocity (see [3, 4]). Hence the most meaningful definition of the “solution of a differential equation” in problems of the dynamics of mechanical systems with sliding friction is that using the concept of right derivative [5].     

Comparison of gas-dynamic models for hypersonic flow past bodies

Various gas-dynamic models for describing chemically non-equilibrium flows are compared using the example of the steady flow past the blunt nose of the “Buran” [1] and “Space Shuttle” vehicles during their descent from orbit. Models of locally self-similar approximations of the Navier-Stokes equations [2], of a chemically equilibrium and non-equilibrium complete viscous shock layer (CVSL) [3] and a model of a thin viscous shock layer (TVSL) [4] are considered. In all the models the occurrence of physicochemical processes was taken into account in the same way using fixed values of the constants for the gas-phase chemical reactions (their effect has been considered in [5]). Good agreement between the results of calculations of the heat flux at the critical point is found.

Chemically non-equilibrium flows have been considered earlier using the approximate Navier-Stokes equations [6], within the framework of a TVSL [7] and a CVSL [8, 9](for more detail, see the review [10]). The TVSL and CVSL models were compared in [11] in the case of flows of a uniform gas.     

On the theory of fugoid motions

In 1891 Zhukovslii in his paper “On soaring of birds” [1] solved the problem of the motion of a body of high lift — drag ratio in an atmosphere of constant density. In [2] this problem was considered in greater detail, but the basic assumption of a constant density was made here as well. There have recently appeared numerous papers concerning the analytical solution of the problem of entry into the atmosphere with orbital and escape velocities [3 to 5]. But these studies were concerned primarily with the problems of ballistic entry and entry with low lift — drag ratio. In considering oscillatory states, the authors limited their treatment to small angles between the trajectory and local horizon. In the present paper we consider the problem without imposing any limitations on the slope of the trajectory or initial velocity. The case examined will be that of a hypothetical glider spacecraft of sufficiently high lift — drag ratio. It is interesting to note that the solution of this problem reduces to the solution of Zhukovskii's problem, but for an atmosphere of variable density. The associated trajectories are termed “fugoid”. All of our assumptions about the parameters of such a glider are of a particular hypothetical character.     

Some remarks concerning the stability of a linear stochastic system

The method for investigating the asymptotic stability in the mean square of a linear stochastic system with Gaussian “white noises” proposed in [1] is developed. Section 1 contains an interpretation of the result obtained [1] in terms of the stability quality criterion employed in controlled systems theory. Section 2 contains the necessary and sufficient conditions of asymptotic stability in the mean square in the Routh-Hurwitz form of a linear stochastic system for the case where the intensities of noises acting in different directions are proportional to each other. This result generalizes the stability conditions given in [1 and 2] ^*.     

Fast reconstruction of Delaunay triangulations

We present a new linear time algorithm to compute a good order for the point set of a Delaunay triangulation in the plane. Such a good order makes reconstruction in linear time with a simple algorithm possible. Similarly to the algorithm of Snoeyink and van Kreveld [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471], our algorithm constructs such orders in O(logn) phases by repeatedly removing a constant fraction of vertices from the current triangulation. Compared to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471] we improve the guarantee on the number of removed vertices in each such phase. If we restrict the degree of the points (at the time they are removed) to 6, our algorithm removes at least 1/3 of the points while the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471] gives a guarantee of 1/10. We achieve this improvement by removing the points sequentially using a breadth first search (BFS) based procedure that—in contrast to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471]—does not (necessarily) remove an independent set.

Besides speeding up the algorithm, removing more points in a single phase has the advantage that two consecutive points in the computed order are usually closer to each other. For this reason, we believe that our approach is better suited for vertex coordinate compression.

We implemented prototypes of both algorithms and compared their running time on point sets uniformly distributed in the unit cube. Our algorithm is slightly faster. To compare the vertex coordinate compression capabilities of both algorithms we round the resulting sequences of vertex coordinates to 16-bit integers and compress them with a simple variable length code. Our algorithm achieves about 14% better vertex data compression than the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471].     

Strange distributionally chaotic triangular maps II

The notion of distributional chaos was introduced by Schweizer and Smítal [Measures of chaos and a spectral decomposition of dynamical systems on the interval, Trans Am Math Soc 1994;344:737–854] for continuous maps of the interval. For continuous maps of a compact metric space three mutually non-equivalent versions of distributional chaos, DC1–DC3, can be considered. In this paper we study distributional chaos in the class of triangular maps of the square which are monotone on the fibres. The main results: (i) If has positive topological entropy then F is DC1, and hence, DC2 and DC3. This result is interesting since similar statement is not true for general triangular maps of the square [Smítal and Štefánková, Distributional chaos for triangular maps, Chaos, Solitons & Fractals 2004;21:1125–8]. (ii) There are which are not DC3, and such that not every recurrent point of F₁ is uniformly recurrent, while F₂ is Li and Yorke chaotic on the set of uniformly recurrent points. This, along with recent results by Forti et al. [Dynamics of homeomorphisms on minimal sets generated by triangular mappings, Bull Austral Math Soc 1999;59:1–20], among others, make possible to compile complete list of the implications between dynamical properties of maps in , solving a long-standing open problem by Sharkovsky.     

Degrevlex Gröbner bases of generic complete intersections

In this paper, we study the Hilbert–Samuel function of a generic standard graded K-algebra

K[X₁,…,X_n]/(g₁,…,g_m)

when refined by an (ℓ)-adic filtration, ℓ being a linear form. From this we obtain a structure theorem which describes the stairs of a generic complete intersection for the degree-reverse-lexicographic order. We show what this means for generic standard (or Gröbner) bases for this order; in particular, we consider an “orderly filling up” conjecture, and we propose a strategy for the standard basis algorithm which could be useful in generic-like cases.     

Central limit theorem behavior in the skew tent map

In this paper we study and establish central limit theorem behavior in the skew (generalized) tent map transformation T: Y →Y originally considered by Billings and Bollt [Billings L, Bollt EM. Probability density functions of some skew tent maps. Chaos, Solitons & Fractals 2001; 12: 365–376] and Ito et al. [Ito S, Tanaka S, Nakada H. On unimodal linear transformations and chaos. II. Tokyo J Math 1979; 2: 241–59]. When the measure ν is invariant under T, the transfer operator governing the evolution of densities f under the action of the skew tent map, as well as the unique stationary density, are given explicitly for specific transformation parameters. Then, using this development, we solve the Poisson equation for two specific integrable observables and explicitly calculate the variance σ()²=∫_Y²(y)ν(dy).     

Group pursuit under bounded evader coordinates

Effective methods are proposed for solving the group pursuit problem with constraints on the evader's state. The paper is closely related to the investigations in /1–4/ (^**) and is a development of the results in /5/ in the case of arbitrary linear equations of motion of the evader.     

A limit theorem for solutions to BSDEs in the space of processes

In this paper, under the most elementary conditions on stochastic differential equations (SDEs in short) and the most elementary conditions on backward stochastic differential equations (BSDEs in short) introduced by Peng, in the space of processes, a limit theorem for solutions to BSDEs with its terminal data being solutions of the SDEs is obtained, based on some recent results of Jiang in the space of random variables in [Jiang, L., 2005a. Converse comparison theorems for backward stochastic differential equations. Statist. Probab. Lett. 71, 173–183; Jiang, L., 2005b. Representation theorems for generators of backward stochastic differential equations. C.R. Acad. Sci. Paris 340 (Ser. I), 161–166; Jiang, L., 2005c. Representation theorems for generators of backward stochastic differential equations and their applications. Stochastic Process. Appl. 115 (12), 1883–1903; Jiang, L., 2005d. Nonlinear expectation—g-expectation theory and its applications in finance. Ph.D Thesis, ShanDong University, China; Jiang, L., 2006. Limit theorem and uniqueness theorem for backward stochastic differential equations. Sci. China Ser. A 49 (10), 1353–1362]. This result generalizes the known results on the limit theorem for solutions to BSDEs in [Jiang, L., 2005a. Converse comparison theorems for backward stochastic differential equations. Statist. Probab. Lett. 71, 173–183; Jiang, L., 2005b. Representation theorems for generators of backward stochastic differential equations. C.R. Acad. Sci. Paris 340 (Ser. I), 161–166; Jiang, L., 2005c. Representation theorems for generators of backward stochastic differential equations and their applications. Stochastic Process. Appl. 115 (12), 1883–1903; Jiang, L., 2005d. Nonlinear expectation—g-expectation theory and its applications in finance. Ph.D Thesis, ShanDong University, China; Jiang, L., 2006. Limit theorem and uniqueness theorem for backward stochastic differential equations. Sci. China Ser. A 49 (10), 1353–1362; Fan, S., 2007. A relationship between the conditional g-evaluation system and the generator g and its applications. Acta Math. Sin. (Engl. Ser.) 23 (8), 1427–1434; Fan, S., 2006. Jensen’s inequality for g-expectation on convex (concave) function. Chinese Ann. Math. Ser. A 27 (5), 635–644 (in Chinese)].     

On small homotopies of loops

Two natural questions are answered in the negative:

• “If a space has the property that small nulhomotopic loops bound small nulhomotopies, then are loops which are limits of nulhomotopic loops themselves nulhomotopic?”

• “Can adding arcs to a space cause an essential curve to become nulhomotopic?”

The answer to the first question clarifies the relationship between the notions of a space being homotopically Hausdorff and π₁-shape injective.

Solution of a problem of Ulam

In this paper we solve the following Ulam problem: “Give conditions in order for a linear mapping near an approximately linear mapping to exist” and establish results involving a product of powers of norms [[5.]; [5.]; [5.]]. There has been much activity on a similar “ -isometry” problem of Ulam [ [1.], 633–636; [2.], 263–277; [4.]]. This work represents an improvement and generalization of the work of [3.], 222–224].     

Automata and logics over finitely varying functions

We extend some of the classical connections between automata and logic due to Büchi (1960) [5] and McNaughton and Papert (1971) [12] to languages of finitely varying functions or “signals”. In particular, we introduce a natural class of automata for generating finitely varying functions called ’s, and show that it coincides in terms of language definability with a natural monadic second-order logic interpreted over finitely varying functions Rabinovich (2002) [15]. We also identify a “counter-free” subclass of ’s which characterise the first-order definable languages of finitely varying functions. Our proofs mainly factor through the classical results for word languages. These results have applications in automata characterisations for continuously interpreted real-time logics like Metric Temporal Logic (MTL) Chevalier et al. (2006, 2007) [6] and [7].     

Discrete subspaces of countably tight compacta

Our main result is that the following cardinal arithmetic assumption, which is a slight weakening of GCH, “2^κ is a finite successor of κ for every cardinal κ”, implies that in any countably tight compactum X there is a discrete subspace D with . This yields a (consistent) confirmation of Alan Dow’s Conjecture 2 from [A. Dow, Closures of discrete sets in compact spaces, Studia Math. Sci. Hung. 42 (2005) 227–234].     

Interval orders based on weak orders

One definition of an interval order is as an order isomorphic to that of a family of nontrivial intervals of a linearly ordered set with [a,b] < [c,d] if b c. Fishburn's theorem states that an order is an interval order if and only if it has no four-element restriction isomorphic to the ordered set (shown in Fig. 1) “ ”. We show that an order is isomorphic to a family of nontrivial intervals of a weak order, ordered as above, if and only if it has no restriction to one of the four ordered sets (shown in Fig. 2) “ ”, a six-element crown or a six-element fence.