Search

We present an asymptotic method to compute efficiently second-order telegraph equations with high-frequency extrinsic oscillations. This method is based on asymptotic expansions in inverse powers of the oscillatory parameter. Each term of this asymptotic expansion is the sum of at most two coefficients. Each coefficient is derived either by recursion or by solving a non-oscillatory problem. This leads to method which exhibit improved performance with growing frequency of oscillation. [ABSTRACT FROM AUTHOR]

Classical separability problem involving multi-color point sets is an important area of study in computational geometry. In this paper, we study different separability problems for bichromatic point set P = P r ∪ P b in R 2 and R 3 , where P r and P b represent a set of n red points and a set of m blue points respectively, and the objective is to compute a monochromatic object of a desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in R 2 , and (ii) an axis-parallel monochromatic cuboid of maximum size in R 3. The time complexities of the algorithms for problems (i) and (ii) are O (m (m + n) (m n + m log m + n log n)) and O (m 3 n + m 2 n log n) , respectively. As a prerequisite, we propose an in-place construction of the classic data structure the k-d tree , that was originally invented by J. L. Bentley in 1975. Our in-place variant of the k -d tree for a set of n points in R k supports orthogonal range counting query using O (1) extra workspace, and with O (n 1 − 1 ∕ k) query time complexity. The construction time of this data structure is O (n log n). Both the construction and query algorithms are non-recursive in nature that do not need O (log n) size recursion stack compared to the previously known construction algorithm for in-place k -d tree and query in it. We believe that this result is of independent interest. We also propose an algorithm for the problem of computing an arbitrarily oriented rectangle of maximum weight among a point set P = P r ∪ P b , where each point in P b (resp. P r) is associated with a negative (resp. positive) real-valued weight that runs in O (m 2 (n + m) log (n + m)) time using O (n) extra space. [ABSTRACT FROM AUTHOR]

We focus on total functions in the theory of reversible computational models. We define a class of recursive permutations, dubbed Reversible Primitive Permutations (RPP) which are computable invertible total endo-functions on integers, so a subset of total reversible computations. RPP is generated from five basic functions (identity, sign-change, successor, predecessor, swap), two notions of composition (sequential and parallel), one functional iteration and one functional selection. RPP is closed by inversion and it is expressive enough to encode Cantor pairing and the whole class of Primitive Recursive Functions. [ABSTRACT FROM AUTHOR]

The Kolmogorov complexity of a string x is defined as the length of a shortest program p of x for some appropriate universal machine U , that is, U (p) = x and p is a shortest string with this property. Neither the plain nor the prefix-free version of Kolmogorov complexity are recursive but for both versions it is well-known that there are recursive exact Solovay functions, that is, recursive upper bounds for Kolmogorov complexity that are infinitely often tight. Let a coding function for a machine M be a function f such that f (x) is always a program of x for M. From the existence of exact Solovay functions it follows easily that for every universal machine there is a recursive coding function that maps infinitely many strings to a shortest program. Extending a recent line of research, in what follows it is investigated in which situations there is a coding function for some universal machine that maps infinitely many strings to the length-lexicographically least program. The main results which hold in the plain as well as in the prefix-free setting are the following. For every universal machine there is a recursive coding function that maps infinitely many strings to their least programs. There is a partial recursive coding function (defined in the natural way) for some universal machine that for every set maps infinitely many prefixes of the set to their least programs. Exactly for every set that is Bennett shallow (not deep), there is a recursive coding function for some universal machine that maps all prefixes of the set to their least programs. Differences between the plain and the prefix-free frameworks are obtained by considering effective sequences I 1 , I 2 , ... of mutually disjoint finite sets and asking for a recursive coding function for some universal machine that maps at least one string in each set I n to its least code. Such coding functions do not exist in the prefix-free setting but exist in the plain setting in case the sets I n are not too small. [ABSTRACT FROM AUTHOR]

Brouwer (1927) claimed that every function from the Baire space to natural numbers is induced by a neighbourhood function whose domain admits bar induction. We show that Brouwer's claim is provable in Heyting arithmetic in all finite types (HA ω) for definable functions of the system. The proof does not rely on elaborate proof theoretic methods such as normalisation or ordinal analysis. Instead, we internalise in HA ω the dialogue tree interpretation of Gödel's system T due to Escardó (2013). The interpretation determines a syntactic translation of terms, which yields a neighbourhood function from a closed term of HA ω with the required property. As applications of this result, we prove some well-known properties of HA ω : uniform continuity of definable functions from N N to N on the Cantor space; closure under the rule of bar induction; and closure of bar recursion for the lowest type with a definable stopping function. [ABSTRACT FROM AUTHOR]

We compare Brouwer's bar theorem and Spector's bar recursion for the lowest type in the context of constructive reverse mathematics. To this end, we reformulate bar recursion as a logical principle stating the existence of a bar recursor for every function which serves as the stopping condition of bar recursion. We then show that the decidable bar induction is equivalent to the existence of a bar recursor for every continuous function from N N to N with a continuous modulus. We also introduce fan recursion, the bar recursion for binary trees, and show that the decidable fan theorem is equivalent to the existence of a fan recursor for every continuous function from { 0 , 1 } N to N with a continuous modulus. The equivalence for bar induction holds over the extensional version of intuitionistic arithmetic in all finite types augmented with the characteristic principles of Gödel's Dialectica interpretation. On the other hand, we show the equivalence for fan theorem without using such extra principles. [ABSTRACT FROM AUTHOR]

Highlights • The proposed filter addresses occlusions and detection loss that exploits the advantages of both detection-based and TBD approaches to improve performance while reducing the computational cost. • In a single Bayesian recursion the filter seamlessly integrates state estimation, track management, clutter rejection, detection loss and occlusion handling as well as prior knowledge that detection loss in the middle of the scene are likely to be due to occlusions. • Tracking performance is compared to state-of-the-art algorithms on simulated data and well-known benchmark video datasets. Abstract This paper proposes an online multi-object tracking algorithm for image observations using a top-down Bayesian formulation that seamlessly integrates state estimation, track management, handling of false positives, false negatives and occlusion into a single recursion. This is achieved by modeling the multi-object state as labeled random finite set and using the Bayes recursion to propagate the multi-object filtering density forward in time. The proposed filter updates tracks with detections but switches to image data when detection loss occurs, thereby exploiting the efficiency of detection data and the accuracy of image data. Furthermore the labeled random finite set framework enables the incorporation of prior knowledge that detection loss in the middle of the scene are likely to be due to occlusions. Such prior knowledge can be exploited to improve occlusion handling, especially long occlusions that can lead to premature track termination in on-line multi-object tracking. Tracking performance is compared to state-of-the-art algorithms on synthetic data and well-known benchmark video datasets. [ABSTRACT FROM AUTHOR]

Abstract An extended equation of dispersive water waves, proposed by Kupershmidt, is considered. By an ansatz on eigenfunctions of its recursion operator, a linear spectral problem, which turns to be type of the energy dependent Schrödinger, is constructed for the system. As by-products, modified systems are presented. Furthermore, a new bi-Hamiltonian system is obtained and shown to be related to a three component generalization of the Camassa–Holm equation under a Miura-type transformation. [ABSTRACT FROM AUTHOR]

Abstract We consider (3+1)-dimensional second-order evolutionary PDEs where the unknown u enters only in the form of the 2nd-order partial derivatives. For such equations which possess a Lagrangian, we show that all of them have the symplectic Monge–Ampère form and determine their Lagrangians. We develop a calculus for transforming the symmetry condition to the "skew-factorized" form from which we immediately extract Lax pairs and recursion relations for symmetries, thus showing that all such equations are integrable in the traditional sense. We convert these equations together with their Lagrangians to a two-component form and obtain recursion operators in a 2 × 2 matrix form. We transform our equations from Lagrangian to Hamiltonian form by using the Dirac's theory of constraints. Composing recursion operators with the Hamiltonian operators we obtain the second Hamiltonian form of our systems, thus showing that they are bi-Hamiltonian systems integrable in the sense of Magri. By this approach, we obtain five new bi-Hamiltonian multi-parameter systems in (3+1) dimensions. [ABSTRACT FROM AUTHOR]

Abstract In recent years, transforming a time series into visibility network has emerged as a powerful tool of data analysis, with applications in many pure and applied domains of statistical physics and non-linear dynamics. The algorithms available for this transform are either very slow or consume copious amount of memory resorting to recursive calls. Here we propose an efficient non-recursive algorithm for constructing natural visibility graph from time series data. In comparison to the recursive method, the new algorithm offers safer and more optimized use of memory space without sacrificing its speed. Performance of this algorithm is tested with a variety of synthetic and experimental time series data-sets. Highlights • A novel sort-and-conquer algorithm is proposed to transform a time series into visibility graph. • Being non-recursive, this algorithm does not use stack frames in memory. • Speed of execution is either comparable or better than the existing divide-and-conquer algorithm. • Memory efficiency is significantly superior to the recursive method. [ABSTRACT FROM AUTHOR]

Abstract We explore the possibility of axiomatic characterization of approval voting when the set of voters is fixed and each voter has a dichotomous preference over the alternatives. We first prove that if the set of alternatives is variable, a social choice rule is approval voting if and only if it satisfies strategy-proofness together with four standard axioms. We then establish a similar characterization in the case of fixed alternatives by introducing a stronger version of strategy-proofness. The latter result answers an open problem left in M. Vorsatz (2007). Highlights • We consider approval voting on a fixed electorate with dichotomous preferences. • We characterize approval voting with variable alternatives by strategy-proofness. • We also establish a characterization in the case of fixed alternatives. • A stronger version of strategy-proofness is the key axiom in the second result. • The second result answers an open problem in the existing literature. [ABSTRACT FROM AUTHOR]

Highlights • Proposed method reduces Kalman filter estimation bias caused by noisy speech input. • The Kalman filter gain is adaptively and dynamically tuned by a robustness metric. • The proposed method is significantly preferred over the other treatment types. Abstract In this paper, we describe a tuning method based on a robustness metric and extended to work with the augmented Kalman filter for enhancing coloured-noise-corrupted speech. The method proposed within utilises the robustness metric to provide dynamic and adaptive tuning of the Kalman filter gain in order to reduce the residual noise that results from poor speech model estimates. An analysis of the Kalman filter recursion equations is presented that augments the robustness metric equations to include coloured noise model parameters. Objective and blind AB subjective listening tests were performed on the NOIZEUS speech corpus for both white and coloured noises with the results being compared with the MMSE method. In the blind AB subjective testing, the 15 English-speaking listeners showed preference for the proposed method over both the MMSE and oracle Kalman filter methods (where clean speech parameters were used). These results imply that the proposed tuned Kalman filter produces more perceptibly-acceptable enhanced speech than the oracle Kalman filter, which is considered the ideal for this enhancement technique. [ABSTRACT FROM AUTHOR]

Highlights • We present an algorithm that transforms context-free grammars into a single set of supercombinators. • We evaluate our algorithm with the use of 62,008 grammar samples obtained from Groningen Meaning Bank. • We have found the limit of supercombinator set, which in case of our sample set is a sequence of Catalan numbers. • We show the way how to identify the most common structures of input grammars. Abstract We present an algorithm that transforms context-free grammars into a non-redundant set of supercombinators. This set contains interconnected lambda calculus' supercombinators that are enriched by grammar operations. The resulting set is scalable and it can be extended with new supercombinators created from grammars. We describe this algorithm in detail and then we apply it on 62,008 grammar samples in order to find out the properties and limits of acquired supercombinator set. We show that this set has a maximum theoretical limit of possible supercombinators. That limit is the sequence of Catalan numbers. We show that in some cases we are able to reach that limit if we use large enough input data source and we limit the size of supercombinators permitted into the final set. We also describe another benefit of our algorithm, which is the identification of most reoccurring structures in the input set. [ABSTRACT FROM AUTHOR]

A super Sasa–Satsuma hierarchy associated with a 3 × 3 matrix spectral problem is proposed with the aid of the zero-curvature equation and Lenard recursion equations. A typical member in the hierarchy is the super Sasa–Satsuma equation. The super bi-Hamiltonian structures of the super Sasa–Satsuma hierarchy are constructed by utilizing the super trace identity. The infinite conservation laws of the super Sasa–Satsuma equation are presented by resorting to the spectral parameter expansion. [ABSTRACT FROM AUTHOR]

The present paper investigates the quality of numberings measured in three different ways: (a) the complexity of finding witnesses of Kleene's Recursion Theorem in the numbering; (b) for which learning notions from inductive inference the numbering is an optimal hypothesis space; (c) the complexity needed to translate the indices of other numberings to those of the given one. In all three cases, one assumes that the corresponding witnesses or correct hypotheses are found in the limit and one measures the complexity with respect to the best criterion of convergence which can be achieved. The convergence criteria considered are those of finite, explanatory, vacillatory and behaviourally correct convergence. The main finding is that the complexity of finding witnesses for Kleene's Recursion Theorem and the optimality for learning are independent of each other. Furthermore, if the numbering is optimal for explanatory learning and also allows to solve Kleene's Recursion Theorem with respect to explanatory convergence, then it also allows to translate indices of other numberings with respect to explanatory convergence. [ABSTRACT FROM AUTHOR]

Rotation symmetric Boolean functions are invariant under circular translation of indices. These functions have very rich cryptographic properties and have been used in different cryptosystems. Recently, Thomas Cusick proved that exponential sums of rotation symmetric Boolean functions satisfy homogeneous linear recurrences with integer coefficients. In this work, a generalization of this result is proved over any Galois field. That is, exponential sums over Galois fields of some rotation symmetric polynomials satisfy linear recurrences with integer coefficients. In the particular case of F 2 , an elementary method is used to obtain explicit recurrences for exponential sums of some of these functions. The concept of trapezoid Boolean function is also introduced and it is showed that the linear recurrences that exponential sums of trapezoid Boolean functions satisfy are the same as the ones satisfied by exponential sums of the corresponding rotations symmetric Boolean functions. Finally, it is proved that exponential sums of trapezoid and symmetric polynomials also satisfy linear recurrences with integer coefficients over any Galois field F q . Moreover, the Discrete Fourier Transform matrix and some Complex Hadamard matrices appear as examples in some of our explicit formulas of these recurrences. [ABSTRACT FROM AUTHOR]

The expanded Aztec diamond is a generalized version of the Aztec diamond, with an arbitrary number of long columns and long rows in the middle. In this paper, we count the number of domino tilings of the expanded Aztec diamond. The exact number of domino tilings is given by recurrence relations of state matrices by virtue of the state matrix recursion algorithm, recently developed by the author to solve various two-dimensional regular lattice model enumeration problems. [ABSTRACT FROM AUTHOR]

We provide a set of conditions which ensure the almost sure convergence of a class of simulated annealing algorithms on a bounded set X ⊂ R d based on a time-varying Markov kernel. The class of algorithms considered in this work encompasses the one studied in Bélisle (1992) and Yang (2000) as well as its derandomized version recently proposed by Gerber and Bornn (2016). To the best of our knowledge, the results we derive are the first examples of almost sure convergence results for simulated annealing based on a time-varying kernel. In addition, the assumptions on the Markov kernel and on the cooling schedule have the advantage of being trivial to verify in practice. [ABSTRACT FROM AUTHOR]

By following the ideas presented by Fukumoto and Miyajima in Fukumoto and Miyajima (1996) we derive a generalized method for constructing integrable nonlocal equations starting from any bi-Hamiltonian hierarchy supplied with a recursion operator. This construction provides the right framework for the application of the full machinery of the inverse scattering transform. We pay attention to the Pohlmeyer–Lund–Regge equation coming from the nonlinear Schrödinger hierarchy and construct the formula for the reflectionless potential solutions which are generalizations of multi-solitons. Some explicit examples are discussed. [ABSTRACT FROM AUTHOR]

A hierarchy of dynamic shell equations is derived for an orthotropic cylindrical shell. The displacement components are expanded into power series in the thickness coordinate and the three-dimensional elastodynamic equations then yield a set of recursion relations among the expansion functions that can be used to eliminate all but the six lowest-order functions. Applying the boundary conditions on the surfaces of the shell and eliminating all but the six lowest-order expansion functions give the shell equations as a power series in the shell thickness. In principle, these six differential equations can be truncated to any order. Numerical examples showing eigenfrequencies for a ring and for a simply supported shell show the convergence of the method to the 3D solution, and a comparison with previous investigations is also made. Finally, the exact 3D solution is given for a simply supported transversely isotropic shell of arbitrary thickness. [ABSTRACT FROM AUTHOR]

In this article we prove that Lax pairs associated with ħ -dependent six Painlevé equations satisfy the topological type property proposed by Bergère, Borot and Eynard for any generic choice of the monodromy parameters. Consequently we show that one can reconstruct the formal ħ -expansion of the isomonodromic τ -function and of the determinantal formulas by applying the so-called topological recursion to the spectral curve attached to the Lax pair in all six Painlevé cases. Finally we illustrate the former results with the explicit computations of the first orders of the six τ -functions. [ABSTRACT FROM AUTHOR]

The effects of saturation-type nonlinearities on the input and the error in the weight update equation for LMS adaptation are investigated for a stationary white Gaussian data model for system identification. Nonlinear recursions are derived for the transient and steady-state weight first and second moments that include the effect of soft limiters on both the input and the error driving the algorithm. By varying a single parameter of the soft limiter, a general theory is presented that is applicable to LMS, soft limiting of the input, error or both and sign–sign LMS. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to state the correct formulation of a theorem proposed by M. Roitman and Z. Rubinstein on the characterization of linear recursions which imply a linear recursion with nonnegative coefficients. The authors present a counterexample to such a theorem and then state its correct formulation. [ABSTRACT FROM AUTHOR]

In this communication we present a detailed study of the effect of chemical disorder on the optical response of Ni 1− x Pt x (0.1 ⩽ x ⩽ 0.75) and Ni 3(1− x )/3 Pt x (0.1 ⩽ x ⩽ 0.3). We shall propose a formalism which will combine a Kubo-Greenwood approach with a DFT based tight-binding linear muffin-tin orbitals (TB-LMTO) basis and augmented space recursion (ASR) technique to explicitly incorporate the effect of disorder. We show that chemical disorder has a large impact on optical response of Ni-Pt systems. In ordered Ni-Pt alloys, the optical conductivity peaks are sharp. But as we switch on chemical disorder, the UV peak becomes broadened and its position as a function of composition and disorder carries the signature of a phase transition from NiPt to Ni 3 Pt with decreasing Pt concentration. Quantitatively this agrees well with Massalski’s Ni-Pt phase diagram (Massalski, 1990). Both ordered NiPt and Ni 3 Pt have an optical conductivity transition at 4.12 eV. But disordered NiPt has an optical conductivity transition at 3.93 eV. If we decrease the Pt content, it results a chemical phase transition from NiPt to Ni 3 Pt and shifts the peak position by 1.67 eV to the ultraviolet range at 5.6 eV. There is a significant broadening of UV peak with increasing Pt content due to enhancement of 3d(Ni)-5d(Pt) bonding. Chemical disorder enhances the optical response of NiPt alloys nearly one order of magnitude. Our study also shows the fragile magnetic effect on optical response of disordered Ni 1− x Pt x (0.4 < x < 0.6) binary alloys. Our theoretical predictions agree reasonably well with both previous experimental findings as well as theoretical investigations. [ABSTRACT FROM AUTHOR]

We show that it is possible, for every machine universal for Kolmogorov complexity, to enumerate the lexicographically least description of a length n string in O ( n ) attempts. In contrast to this positive result for strings, we find that, in any Kolmogorov numbering, no enumerator of nontrivial size can generate a list containing the minimal index of a given partial-computable function. One cannot even achieve a laconic enumerator for nearly -minimal indices of partial-computable functions. [ABSTRACT FROM AUTHOR]

Classical Hurwitz numbers count branched covers of the Riemann sphere with prescribed ramification data, or equivalently, factorisations in the symmetric group with prescribed cycle structure data. Monotone Hurwitz numbers restrict the enumeration by imposing a further monotonicity condition on such factorisations. In this paper, we prove that monotone Hurwitz numbers arise from the topological recursion of Eynard and Orantin applied to a particular spectral curve. We furthermore derive a quantum curve for monotone Hurwitz numbers. These results extend the collection of enumerative problems known to be governed by the paradigm of topological recursion and quantum curves, as well as the list of analogues between monotone Hurwitz numbers and their classical counterparts. [ABSTRACT FROM AUTHOR]

Two integrable U ( 1 ) -invariant peakon equations are derived from the NLS hierarchy through the tri-Hamiltonian splitting method. A Lax pair, a recursion operator, a bi-Hamiltonian formulation, and a hierarchy of symmetries and conservation laws are obtained for both peakon equations. These equations are also shown to arise as potential flows in the NLS hierarchy by applying the NLS recursion operator to flows generated by space translations and U ( 1 ) -phase rotations on a potential variable. Solutions for both equations are derived using a peakon ansatz combined with an oscillatory temporal phase. This yields the first known example of a peakon breather. Spatially periodic counterparts of these solutions are also obtained. [ABSTRACT FROM AUTHOR]

The goal of this paper is to examine the possible neurobiological basis of a defining property of the human language faculty: recursion. I suggest that recursion should be understood in light of Darwinian's descent with modification. Descent: that is, based on ingredients of neural circuitry found in ‘non-linguistic’ species; and modification: a reconfiguration that is specific to anatomically modern humans. I argue that the expansion of the parietal region associated with the globularization of the neurocranium in our species contributed to the transformation of the connection between Broca's and Wernicke's region via Geschwind's territory, and enabled the pairing of evolutionary ancient networks that together became capable of constructing and processing not just sequences, but sequences of sequences. [ABSTRACT FROM AUTHOR]

Theory of mind, also known as mentalising, meta-representation, second-order intentionality, or mindreading is the ability to attribute and reflect on the mental states of others. A number of investigators have noted that an important relationship exists between child language development and children’s understanding of second-order intentionality. However, although the ontogeny of theory of mind has been extensively studied over the past few decades, only recently have we begun to understand more concerning the limits of human mentalising ability in adults. For example, several studies have shown that the limits of mentalising ability for normal adults are consistently placed around fifth-order intentionality (i.e. I believe that you suppose that I imagine that you want me to believe that...), forming a naturally recursive hierarchy which corresponds to increasingly embedded mindreading. Moreover, several psychologists have recently suggested the adult capacity for higher-order intentionality may have played a critical role in the evolution of language, including especially the ability for recursive syntax comprehension and production, according to a cognitive bootstrapping effect. Here, we used the Imposing Memory Task (n = 210 female and 204 male adults) to analyse the association and interaction between higher-order intentionality capacity and performance on a recursive syntax measure. Multiple regression analyses indicated that recursive syntax abilities are lower than mindreading competences below fifth-order, but then reverses at higher values. In addition, a path analysis further suggested intentionality capacity as the likely causal variable. Thus, these results seem to suggest that first-order through fifth-order intentionality is necessary to assist the processing of simpler syntactic structures, but beyond fifth-order intentionality the cognitive scaffolding provided by recursive syntax may be engaged to enable higher-order mentalising. In summary, this may explain in part how and why many modern languages exhibit recursive syntax. [ABSTRACT FROM AUTHOR]

Many multi-robot problems require the achievement of formations as part of the overall mission. This work considers a scenario in which unlabeled homogeneous robots must adopt a given formation pattern buildable anywhere in the environment. This involves finding the relative pose of the formation in regard to the initial robot positions, understood as a translation and a rotation; and the optimal assignment of the role of each robot within the formation. This paper provides an optimal solution for the combined parameters of translation, rotation and assignment that minimizes total displacement. To achieve this objective we first formally prove that the three decision variables are separable. Since computing the optimal assignment without accounting for the rotation is a computationally expensive problem, we propose an algorithm that efficiently computes the optimal roles together with the rotation. The algorithm is provably correct and finds the optimal solution in finite time. A distributed implementation is also discussed. Simulation results characterize the complexity of our solution and demonstrate its effectiveness. [ABSTRACT FROM AUTHOR]

This paper aims at providing theta function representation of all algebro-geometric solutions and related quantities for the Fokas–Olver–Rosenau–Qiao (FORQ, sometimes also called the modified Camassa–Holm (MCH) in the literature) hierarchy and studying their algebro-geometric initial value problem. Our main tools include the polynomial recursion formalism to derive the FORQ hierarchy, the hyperelliptic curve K n of arithmetic genus n , the Baker–Akhiezer functions, the meromorphic function ϕ , the Dubrovin-type equations for auxiliary divisors and the associated trace formulas. With the help of these tools, the explicit theta function representations of the Baker–Akhiezer functions, the meromorphic function and the algebro-geometric solutions are obtained for the entire FORQ hierarchy. [ABSTRACT FROM AUTHOR]

In this paper, extensions for the Conjugate Gradient Least Squares (CGLS) algorithm in block forms, so-called Block Conjugate Gradient Least Squares (BCGLS), are described. Block parameter matrices are designed to explore the block Krylov subspace so that multiple right-hand sides can be treated simultaneously, while maintaining orthogonality and minimization properties along iterations. Search subspace is reduced adaptively in case of (near) rank deficiency to prevent breakdown. A deflated form of BCGLS is developed to accelerate convergence. Numerical examples demonstrate effectiveness in handling rank deficiency and efficiency in convergence accelerations in these BCGLS forms. [ABSTRACT FROM AUTHOR]

This paper is devoted to the computation of US-eigenpairs of complex symmetric tensors and U-eigenpairs of complex tensors. Based on the Takagi factorization of complex symmetric matrices, we derive an iterative algorithm for computing US-eigenpairs of complex symmetric tensors, denoted as QRCST Algorithm . We also observe that multiple US-eigenpairs can be found from a local permutation heuristic, which is effectively a tensor similarity transformation, resulting in the permuted version of QRCST. We then generalize our techniques to general complex tensors. Finally, we derive a higher order power type method for computing a US- or a U-eigenpair, similar to the higher-order power method for computing Z-eigenpairs of real symmetric tensors or a best rank-one approximation of real tensors. We illustrate our algorithms via numerical examples. [ABSTRACT FROM AUTHOR]

We discover two additional Lax pairs and three nonlocal recursion operators for symmetries of the general heavenly equation introduced by Doubrov and Ferapontov. Converting the equation to a two-component form, we obtain Lagrangian and Hamiltonian structures of the two-component general heavenly system. We study all point symmetries of the two-component system and, using the inverse Noether theorem in the Hamiltonian form, obtain all the integrals of motion corresponding to each variational (Noether) symmetry. We discover that in the two-component form we have only a single nonlocal recursion operator. Composing the recursion operator with the first Hamiltonian operator we obtain second Hamiltonian operator. We check the Jacobi identities for the second Hamiltonian operator and compatibility of the two Hamiltonian structures using P. Olver’s theory of functional multi-vectors. Our well-founded conjecture is that P. Olver’s method works fine for nonlocal operators. We show that the general heavenly equation in the two-component form is a bi-Hamiltonian system integrable in the sense of Magri. We demonstrate how to obtain nonlocal Hamiltonian flows generated by local Hamiltonians by using formal adjoint recursion operator. [ABSTRACT FROM AUTHOR]

With the fast development of hydropower in China, a group of hydropower stations has been put into operation in the past few decades and the hydropower system scale is experiencing a booming period. Hence, the “curse of dimensionality” is posing a great challenge to the optimal operation of hydropower system (OOHS) because the computational cost grows exponentially with the increasing number of plants. Discrete differential dynamic programming (DDDP) is a classical method to alleviate the dimensionality problem of dynamic programming for the OOHS, but its memory requirement and computational time still grows exponentially with the increasing number of plants. In order to improve the DDDP performance, a novel method called orthogonal discrete differential dynamic programming (ODDDP) is introduced to solve the OOHS problem. In ODDDP, orthogonal experimental design is employed to select some small but representative state combinations when constructing the corridor around the current trajectory, and then dynamic programming recursion equation is used to find an improved trajectory for the next iteration. The proposed method is applied to the optimal operation of a large-scale hydropower system in China. The results indicate that compared to the standard DDDP, ODDDP only needs about 0.37% of computing time to obtain the results with about 99.75% of generation in the hydropower system with 7 plants and 3 states per plant, providing a new effective tool for large-scale OOHS problem. [ABSTRACT FROM AUTHOR]

In this article we suggest a new systematic approach to studying algorithms on algebraic structures via primitive recursion. The approach is designed to fill the gap between abstract computable structure theory and feasible (in the sense of polynomial-time, computational or automatic) algebra. [ABSTRACT FROM AUTHOR]

The Tamari lattices have been intensely studied since their introduction by Dov Tamari around 1960. However oddly enough, a formula for the number of maximal chains is still unknown. This is due largely to the fact that maximal chains in the n th Tamari lattice T n range in length from n − 1 to n 2 . In this note, we treat vertices in the lattice as Young diagrams and identify maximal chains as certain tableaux. For each i ≥ − 1 , we define C i ( n ) as the set of maximal chains in T n of length n + i . We give a recursion for # C i ( n ) and an explicit formula based on predetermined initial values. The formula is a polynomial in n of degree 3 i + 3 . For example, the number of maximal chains of length n in T n is # C 0 ( n ) = n 3 . The formula has a combinatorial interpretation in terms of a special property of maximal chains. [ABSTRACT FROM AUTHOR]

We consider the problem of selecting an optimal set of sensors to estimate the states of linear dynamical systems. Specifically, the goal is to choose (at design-time) a subset of sensors (satisfying certain budget constraints) from a given set in order to minimize the trace of the steady state a priori or a posteriori error covariance produced by a Kalman filter. We show that the a priori and a posteriori error covariance-based sensor selection problems are both NP-hard, even under the additional assumption that the system is stable. We then provide bounds on the worst-case performance of sensor selection algorithms based on the system dynamics, and show that greedy algorithms are optimal for a certain class of systems. However, as a negative result, we show that certain typical objective functions are not submodular or supermodular in general. While this makes it difficult to evaluate the performance of greedy algorithms for sensor selection (outside of certain special cases), we show via simulations that these greedy algorithms perform well in practice. [ABSTRACT FROM AUTHOR]

We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct constructions using martingales. At the same time, we introduce the concept of i.o. subuniformity and relate this concept to recursive measure theory. We prove that there are classes closed downwards under Turing reducibility that have recursive measure zero and that are not i.o. subuniform. This shows that there are examples of classes that cannot be covered with methods other than probabilistic ones. It is easily seen that every set of hyperimmune degree can cover the recursive sets. We prove that there are both examples of hyperimmune-free degree that can and that cannot compute such a cover. [ABSTRACT FROM AUTHOR]

The human ability to process hierarchical structures has been a longstanding research topic. However, the nature of the cognitive machinery underlying this faculty remains controversial. Recursion, the ability to embed structures within structures of the same kind, has been proposed as a key component of our ability to parse and generate complex hierarchies. Here, we investigated the cognitive representation of both recursive and iterative processes in the auditory domain. The experiment used a two-alternative forced-choice paradigm: participants were exposed to three-step processes in which pure-tone sequences were built either through recursive or iterative processes, and had to choose the correct completion. Foils were constructed according to generative processes that did not match the previous steps. Both musicians and non-musicians were able to represent recursion in the auditory domain, although musicians performed better. We also observed that general 'musical' aptitudes played a role in both recursion and iteration, although the influence of musical training was somehow independent from melodic memory. Moreover, unlike iteration, recursion in audition was well correlated with its non-auditory (recursive) analogues in the visual and action sequencing domains. These results suggest that the cognitive machinery involved in establishing recursive representations is domain-general, even though this machinery requires access to information resulting from domain-specific processes. [ABSTRACT FROM AUTHOR]

We present a recursion scheme based on attribute grammars that can be transparently applied to trees and acyclic graphs. Our recursion scheme allows the programmer to implement a tree traversal or a tree transformation and then apply it to compact graph representations of trees instead. The resulting graph traversal or graph transformation avoids recomputation of intermediate results for shared nodes – even if intermediate results are used in different contexts. Consequently, this approach leads to asymptotic speedup proportional to the compression provided by the graph representation. In general, however, this sharing of intermediate results is not sound. Therefore, we complement our implementation of the recursion scheme with a number of correspondence theorems that ensure soundness for various classes of traversals. We illustrate the practical applicability of the implementation as well as the complementing theory with a number of examples. [ABSTRACT FROM AUTHOR]

We firstly present an evaluation problem for online shop based on gradually increasing number of inputs. Then we propose a model using Recursive OWA operator with constant orness/andness grade involved. Next, we analyze properties of discrete Recursive OWA operators, show their relationship with Pascal Triangle and further generalize this relationship to Γ function. For the continuous case, we propose a concept of self-similar ordered weighting functions (OWF) and analyze some properties of OWF. Using these concepts, we present the recursive aggregation method of continuous arguments under continuous OWF. We show a relationship of OWF with the Regular Increasing (RIM) quantifier. Furthermore, based on an isomorphism relation between discrete and continuous recursive OWA operators, Left Recursive OWA can be seen as the discrete form of continuous OWF. [ABSTRACT FROM AUTHOR]

We study the affine recursion X n = A n X n − 1 + B n where ( A n , B n ) ∈ R + × R is an i.i.d. sequence and recursions X n = Φ n ( X n − 1 ) defined by Lipschitz transformations such that Φ ( x ) ≥ A x + B . It is known that under appropriate hypotheses the stationary solution X has regularly varying tail, i.e. lim t → ∞ t α P [ X > t ] = C . However positivity of C in general is either unknown or requires some additional involved arguments. In this paper we give a simple proof that C > 0 . This applies, in particular, to the case when Kesten–Goldie assumptions are satisfied. [ABSTRACT FROM AUTHOR]

The renormalized simplified model is proposed to investigate indirectly how the static structure factor plays an important role in renormalizing a quadratic nonlinear term in the ideal mode-coupling memory function near the glass transition. The renormalized simplified recursion equation is then derived based on the time-convolutionless mode-coupling theory (TMCT) proposed recently by the present author. This phenomenological approach is successfully applied to check from a unified point of view how strong liquids are different from fragile liquids. The simulation results for those two types of liquids are analyzed consistently by the numerical solutions of the recursion equation. Then, the control parameter dependence of the renormalized nonlinear exponent in both types of liquids is fully investigated. Thus, it is shown that there exists a novel difference between the universal behavior in strong liquids and that in fragile liquids not only for their transport coefficients but also for their dynamics. [ABSTRACT FROM AUTHOR]

In this paper, we calculate the Hosoya index in a family of deterministic recursive trees with a special feature that includes new nodes which are connected to existing nodes with a certain rule. We then obtain a recursive solution of the Hosoya index based on the operations of a determinant. The computational complexity of our proposed algorithm is O ( log 2 n ) with n being the network size, which is lower than that of the existing numerical methods. Finally, we give a weighted tree shrinking method as a graphical interpretation of the recurrence formula for the Hosoya index. [ABSTRACT FROM AUTHOR]

The present work investigates inductive inference from the perspective of reverse mathematics. Reverse mathematics is a framework that allows gauging the proof strength of theorems and axioms in many areas of mathematics. The present work applies its methods to basic notions of algorithmic learning theory such as Angluin's tell-tale criterion and its variants for learning in the limit and for conservative learning, as well as to the more general scenario of partial learning. These notions are studied in the reverse mathematics context for uniformly and weakly represented families of languages. The results are stated in terms of axioms referring to induction strength and to domination of weakly represented families of functions. [ABSTRACT FROM AUTHOR]

Hjorth and Nies proposed notions of randomness corresponding to the higher recursion setting. In particular, they defined the notion of Π 1 1 -Martin-Löf randomness. In this article we present examples of Π 1 1 -Martin-Löf random reals which are obtained as measures of Π 1 1 open sets. [ABSTRACT FROM AUTHOR]