Search

We consider the problem of electrical properties of an m × n cylindrical network with two arbitrary boundaries, which contains multiple topological network models such as the regular cylindrical network, cobweb network, globe network, and so on. We deduce three new and concise analytical formulae of potential and equivalent resistance for the complex network of cylinders by using the RT-V method (a recursion-transform method based on node potentials). To illustrate the multiplicity of the results we give a series of special cases. Interestingly, the results obtained from the resistance formulas of cobweb network and globe network obtained are different from the results of previous studies, which indicates that our research work creates new research ideas and techniques. As a byproduct of the study, a new mathematical identity is discovered in the comparative study. [ABSTRACT FROM AUTHOR]

A new recursive algorithm is proposed for multiplying matrices of order n = 2q (q > 1). This algorithm is based on a fast hybrid algorithm for multiplying matrices of order n = 4μ with μ = 2q−1 (q > 0). As compared with the well-known recursive Strassen's and Winograd–Strassen's algorithms, the new algorithm minimizes the multiplicative complexity equal to Wm ≈ 0.932n2.807 multiplication operations at recursive level d = log2n−3 by 7% and reduces the computation vector by three recursion steps. The multiplicative complexity of the algorithm is estimated. [ABSTRACT FROM AUTHOR]

Several articles deal with tilings with squares and dominoes on 2-dimensional boards, but only a few on boards in 3-dimensional space. We examine a tiling problem with coloured cubes and bricks on a (2 × 2 × n) -board in three dimensions. After a short introduction and the definition of breakability we show a way to get the number of the tilings of an n-long board considering the (n − 1) -long board. It describes recursively the number of possible breakable and unbreakable tilings. Finally, we give some identities for the recursions using breakability. [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 range of possible ordinal values for the Cantor–Bendixson rank of an effectively closed set in Cantor space, and the relationship between the ranks and the Turing degrees of its members, have been closely studied. The wide array of results on this topic have often made use of useful topological features of Cantor space (notably, compactness) and of key properties of computable well-orders. In this paper, a number of these results are extended to the case of Cantor space on the first uncountable ordinal, in which these properties do not hold, using admissible recursion theory. [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]

We consider the problem of electrical properties of an m × n cylindrical network with two arbitrary boundaries, which contains multiple topological network models such as the regular cylindrical network, cobweb network, globe network, and so on. We deduce three new and concise analytical formulae of potential and equivalent resistance for the complex network of cylinders by using the RT-V method (a recursion-transform method based on node potentials). To illustrate the multiplicity of the results we give a series of special cases. Interestingly, the results obtained from the resistance formulas of cobweb network and globe network obtained are different from the results of previous studies, which indicates that our research work creates new research ideas and techniques. As a byproduct of the study, a new mathematical identity is discovered in the comparative study. [ABSTRACT FROM AUTHOR]

We prove the first, even superpolynomial, lower bounds on the size of tropical (min,+) and (max,+) circuits approximating given optimization problems. Many classical dynamic programming (DP) algorithms for optimization problems are pure in that they only use the basic min, max, + operations in their recursion equations. Tropical circuits constitute a rigorous mathematical model for this class of algorithms. An algorithmic consequence of our lower bounds for tropical circuits is that the approximation powers of pure DP algorithms and greedy algorithms are incomparable. That pure DP algorithms can hardly beat greedy in approximation is long known. New in this consequence is that the converse also holds. [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]

In this paper, I present an argument based on empirical data from depictive secondary predication in Standard Arabic (SA) for the assumption that the light v is merged with discourse features that V inherits at some point of derivation (Miyagawa 2010; Jimenez Fernandez & Spyropoulos 2013). The depictive structure in SA exhibits different word order permutations that correspond to the discourse properties of the structure. As such, SA manifests itself as a discourse‐agreement language with discourse and phi‐agreement features on the phase head (e.g., C or v) being transferred into relevant heads of phase complements (e.g., T or V). Such an environment triggers the different rearrangements of the depictive phrase within the vP under Last Resort. To enable movement out of the non‐subcategorized structure of the adjunct small clause, I employ a sideward movement strategy (Nunes 1995, 2001, 2004) to derive the pattern in question.1 [ABSTRACT FROM AUTHOR]

In this work, we present a general formulation for the evaluation of many-electron integrals which arise when traditional one particle expansions are augmented with explicitly correlated Gaussian geminal functions. The integrand is expressed as a product of charge distributions, one for each electron, multiplied by one or more Gaussian geminal factors. Our formulation begins by focusing on the quadratic form that arises in the general n-electron integral. Using the Rys polynomial method for the evaluation of potential energy integrals, we derive a general formula for the evaluation of any n-electron integral. This general expression contains four parameters ω, θ, v, and h, which can be evaluated by an examination of the general quadratic form. Our analysis contains general expressions for any n-electron integral over s-type functions as well as the recursion needed to build up arbitrary angular momentum. The general recursion relation requires at most n + 1 terms for any n-electron integral. To illustrate the general method, we develop explicit expressions for the evaluation of two, three, and four particle electron repulsion integrals as well as two and three particle overlap and nuclear attraction integrals. We conclude our exposition with a discussion of a preliminary computational implementation as well as general computational requirements. Implementation on parallel computers is briefly discussed. [ABSTRACT FROM AUTHOR]

As a popular tool in exploring free energy landscapes, the metadynamics method has been widely applied to elucidate various chemical or biochemical processes. As deeply discussed by Laio et al. [J. Phys. Chem. B 109, 6714 (2005)], the size of the updating Gaussian function is pivotal to the free energy convergence toward the target free energy surface. For instance, a greater Gaussian height can facilitate the quick visit of a conformation region of interest; however, it may lead to a larger error of the calculated free energy surface. In contrast, a lower Gaussian height can guarantee a better resolution of the calculated free energy surface; however, it will take longer time for such a simulation to navigate through the defined conformational region. In order to reconcile such confliction, the authors present a method by implementing the Wang-Landau recursion scheme in the metadynamics simulations to adaptively update the height of the unit Gaussian function. As demonstrated in their model studies on both a toy system, and a realistic molecular system treated with the hybrid quantum mechanical and molecular mechanical (QM/MM) potential, the present approach can quickly result in more decently converged free energy surfaces, compared with the classical metadynamics simulations employing the fixed Gaussian heights. [ABSTRACT FROM AUTHOR]

An efficient computational scheme for calculating highly excited vibrational eigenstates is proposed, combining a Richardson-Leja spectral filter with a novel version of the Davidson method [J. Comput. Phys. 17, 87 (1975)]. Highly excited eigenstates of the Rb2 and H2O molecules are computed to test and verify the method. On the average less than 2.5 outer recursions per eigenstate are needed. For each outer Davidson recursion, less than 20 inner filter recursions per eigenstate are needed on the average. [ABSTRACT FROM AUTHOR]

In the rotation based fast multipole method the accurate determination of the Wigner rotation matrices is essential. The combination of two recurrence relations and the control of the error accumulations allow a very precise determination of the Wigner rotation matrices. The recurrence formulas are simple, efficient, and numerically stable. The advantages over other recursions are documented. [ABSTRACT FROM AUTHOR]

Demonstrates recursion relationships between carbon-carbon and carbon-deuterium order parameters in saturated and unsaturated lipid acyl chains in biomembranes. Use of the order tension method; Revelation of an average bent orientation of the beginning of the chain; Application of formalism to cis or trans unsaturated lipid.

In this article, we introduce Moschovakis higher-order type theory of acyclic recursion L ar λ . We present the potentials of L ar λ for incorporating different reduction systems in L ar λ , with corresponding reduction calculi. At first, we introduce the original reduction calculus of L ar λ , which reduces L ar λ -terms to their canonical forms. This reduction calculus determines the relation of referential, i.e., algorithmic, synonymy between L ar λ -terms with respect to a chosen semantic structure. Our contribution is the definition of a (γ) rule and extending the reduction calculus of L ar λ and its referential synonymy to γ-reduction and γ-synonymy, respectively. The γ-reduction is very useful for simplification of terms in canonical forms, by reducing subterms having superfluous λ-abstraction and corresponding functional applications. Typically, such extra λ abstractions can be introduced by the λ-rule of the reduction calculus of L ar λ . [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 For which sets A does there exist a mapping, computed by a total or partial recursive function, such that the mapping, when its domain is restricted to A , is a 1-to-1, onto mapping to Σ ⁎ ? For which sets A does there exist such a mapping that respects the lexicographical ordering within A ? Both cases are types of perfect, minimal hash functions. The complexity-theoretic versions of these notions are known as compression functions and ranking functions. This paper defines and studies the recursion-theoretic versions of compression and ranking functions, and in particular studies which sets have, or lack, such functions. Thus this is a case where, in contrast to the usual direction of notion transferal, notions from complexity theory are inspiring notions, and an investigation, in computability theory. We show that the rankable and compressible sets broadly populate the 1-truth-table degrees, and we prove that every nonempty coRE cylinder is recursively compressible. [ABSTRACT FROM AUTHOR]

Abstract A group presentation is said to have rational growth if its growth series represents a rational function, which reflects a kind of recursion in the structure of the group. A long-standing open question asks whether the Heisenberg group has rational growth for all finite generating sets, and we settle this question affirmatively. We also establish almost-convexity for all finite generating sets. Previously, both of these properties were known to hold for hyperbolic groups and virtually abelian groups, and there were no further examples in either case. Our main method is a close description of the relationship between word metrics and associated Carnot–Carathéodory Finsler metrics on the ambient Lie group. We provide (non-regular) languages of geodesics in any word metric that represent each group element uniquely. [ABSTRACT FROM AUTHOR]

We examine the growth behaviour of the entries occurring in n-periodic tame friezes of real numbers. Extending work of the last author, we prove that generalised recursive relations exist between all entries of such friezes. These recursions are parametrised by a sequence of so-called growth coefficients, which is itself shown to satisfy a recursive relation. Thus, all growth coefficients are determined by a principal growth coefficient, which can be read-off directly from the frieze. We place special emphasis on periodic tame friezes of positive integers, specifying the values the growth coefficients take for any such frieze. We establish that the growth coefficients of the pair of friezes arising from a triangulation of an annulus coincide. The entries of both are shown to grow asymptotically exponentially, while triangulations of a punctured disc are seen to provide the only friezes of linear growth. [ABSTRACT FROM AUTHOR]

We show how to modify the tree-based methodology to construct a combinatorial interpretation for certain non-monotonic solutions to recursions in the generalized Golomb family. Using this combinatorial interpretation we derive the asymptotic properties of these solutions. [ABSTRACT FROM AUTHOR]

We present a new, syntax-directed framework for Curry-style type systems with subtyping. It supports a rich set of features, and allows for a reasonably simple theory and implementation. The system we consider has sum and product types, universal and existential quantifiers, and inductive and coinductive types. The latter two may carry size invariants that can be used to establish the termination of recursive programs. For example, the termination of quicksort can be derived by showing that partitioning a list does not increase its size. The system deals with complex programs involving mixed induction and coinduction, or even mixed polymorphism and (co-)induction. One of the key ideas is to separate the notion of size from recursion. We do not check the termination of programs directly, but rather show that their (circular) typing proofs are well-founded. Termination is then obtained using a standard (semantic) normalisation proof. To demonstrate the practicality of the system, we provide an implementation accepting all the examples discussed in the article. [ABSTRACT FROM AUTHOR]

In the EDGE BIPARTIZATION problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. Guo et al. (J Comput Syst Sci 72(8):1386-1396, 2006) proposed an algorithm solving this problem in time O(2k·m2); today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for EDGE BIPARTIZATION that works in time O(1.977k·nm), which is the first algorithm with the running time dependence on the parameter better than 2k. To this end, we combine the general iterative compression strategy of Guo et al.  (2006), the technique proposed by Wahlström (in: Proceedings of SODA'14, SIAM, 2014) of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree. [ABSTRACT FROM AUTHOR]

This paper is a follow-up to [4], in which a mistake in [6] (which spread also to [9]) was corrected. We give a strenghtening of the main result on the semantical nonconservativity of the theory of PT− with internal induction for total formulae (PT− + INT(tot), denoted by PT− in [9]). We show that if to PT− the axiom of internal induction for all arithmetical formulae is added (giving PT− + INT), then this theory is semantically stronger than PT−+ INT(tot). In particular the latter is not relatively truth definable (in the sense of [11]) in the former. Last but not least, we provide an axiomatic theory of truth which meets the requirements put forward by Fischer and Horsten in [9]. The truth theory we define is based on Weak Kleene Logic instead of the Strong one. [ABSTRACT FROM AUTHOR]

We sketch a broadening of the Gupta-Belnap notion of a circular or revision theoretic definition into that of a more generalized form incorporating ideas of Kleene's generalized or higher type recursion. This thereby connects the philosophically motivated, and derived, notion of a circular definition with an older form of definition by recursion using functionals, that is functions of functions, as oracles. We note that Gupta and Belnap's notion of 'categorical in L' can be formulated in at least one of these schemes. [ABSTRACT FROM AUTHOR]

The accurate description of contact characteristics between tire and road surface may significantly affect the vehicle motion simulation and control analysis. Based on the LuGre tire model, the pressure distribution function of loading is modified as a non-uniform distribution pattern through new method of recursion formula. The mathematical expression of modified LuGre tire model is achieved through introducing the Bouc-Wen model to reflect tire hysteresis behavior, which takes into consideration the process of dynamic effect of tire vertical loading and tire footprint length. The effectiveness of model is verified through comparison with classic magic formula (MF) and LuGre tire model. Furthermore, the stability of solution for the modified LuGre tire model in the prediction of tire force and alignment torque is demonstrated in frequency domain. Finally, a nonlinear four-DOF vehicle handling dynamics model is built. The front wheel steering angle and the rotational angular velocities of the six tire from a calibrated virtual vehicle is entered into the vehicle model system with modified LuGre tire model as input data. The responses of longitudinal velocity, lateral velocity, yaw rate and roll angle are obtained under two kinds of limit conditions. The comparison results demonstrate the correctness and effectiveness of the built model, which further prove that the modified LuGre tire model is applicable for handling performance analysis of vehicle system. [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]

We use the Tridiagonal Representation Approach (TRA) to obtain exact scattering and bound states solutions of the Schrödinger equation for short-range inverse-square singular hyperbolic potentials. The solutions are series of square integrable functions written in terms of the Jacobi polynomial with the Wilson polynomial as expansion coefficients. The series is finite for the discrete bound states and infinite but bounded for the continuum scattering states. [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]

Starting with a discrete 3 x 3 matrix spectral problem, the hierarchy of Bogoyavlensky lattices which are pure differential-difference equations are derived with the aid of the Lenard recursion equations and the stationary discrete zero-curvature equation. By using the characteristic polynomial of Lax matrix for the hierarchy of stationary Bogoyavlensky lattices, we introduce a trigonal curve Km-1 of arithmetic genus m - 1 and a basis of holomorphic differentials on it, from which we construct the Riemann theta function of the trigonal curve, the related Baker-Akhiezer function, and an algebraic function carrying the data of the divisor. Based on the theory of trigonal curves, the Riemann theta function representations of the Baker-Akhiezer function, the meromorphic function, and in particular, that of solutions of the hierarchy of Bogoyavlensky lattices are obtained. [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]

We study how the shelling components behave under the pyramid and prism operations. As a consequence we obtain a concise recursion for the cubical shelling contributions. [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]

Let E be a Σ1¹ equivalence relation on 2ω which does not have perfectly many equivalence classes. For a ∈ 2ω, define LaE to be the set {[x]E : (∃y)(y ∈ [x]E and ω1 = ω1a)}. For a Turing cone of a's, LaE is countable. This is proved assuming Π2¹-determinacy. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to give a decorated version of the Eynard-Orantin topological recursion using a 2D Topological Quantum Field Theory. We define a kernel for a 2D TQFT and use an algebraic reformulation of a topological recursion to define how to decorate a standard topological recursion by a 2D TQFT. The A-model side enumerative problem consists of counting cell graphs where in addition vertices are decorated by elements in a Frobenius algebra, and which are a decorated version of the generalized Catalan numbers. We show that the function that counts these decorated graphs, which is a decoration of the counting function of the generalized Catalan numbers by a Frobenius algebra, satisfies a topological recursion with respect to the edge-contraction axioms. The path we follow to pass from the A-model side to the remodeled B-model side is to use a discrete Laplace transform as a mirror symmetry map. We show that a decorated version by a 2D TQFT of the Eynard-Orantin differentials satisfies a decorated version of the Eynard-Orantin recursion formula. We illustrate these results using a toy model for the theory arising from the orbifold cohomology of the classifying space of a finite group. In this example, the graphs are orbifold cell graphs (graphs drawn on an orbifold punctured Riemann surface) defined out of the moduli space Mg,n(BG) of stable morphisms from twisted curves to the classifying space of a finite group G. In particular we show that the cotangent class intersection numbers on the moduli space Mg,n(BG) satisfy a decorated Eynard-Orantin topological recursion and we derive an orbifold DVV equation as a consequence of it. This proves from a different perspective the known result which states that the ψ-class intersection numbers on Mg,n(BG) satisfy the Virasoro constraint condition. [ABSTRACT FROM AUTHOR]

We introduce a construction of a set of code sequences {Cn(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {Cn(m)} is a generalization of polar codes presented by Arıkan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n − 1) and N(n − m), and {Cn(m)} coincides with the original polar codes when m = 1. We show that {Cn(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error Pe of {Cn(m)} and show that Pe=O(2−Nβ) is achievable for β < 1/[1+m(ϕ − 1)], where ϕ ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρm − ρm − 1 − 1. The encoding and decoding complexities of {Cn(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Arıkan's construction. [ABSTRACT FROM AUTHOR]

There is considerable interest in constructing succinct programs and much debate over which languages are most expressive. However, such debates tend to revolve around syntactic notions of program size and language constructs, without considering the complex interrelations of syntax, semantics, and implementation. We hypothesise that languages with larger semantics have more succinct programs. To explore this, we have conducted an empirical study of the expressive properties of Turing and Random Access Stored Program machines, taking into account their Structural Operational Semantics, universal machines, implementations in each other, and physical realisations as Field Programmable Gate Arrays (FPGAs). We conclude that our intuitions about the relationship between the expressiveness of a language and the typical succinctness of programs are largely correct. We also conclude that the information content of abstract models of computations is a good indicator of the component count for FPGA realisations. [ABSTRACT FROM AUTHOR]

Monotone recurrence relations give rise to a class of dynamical systems on the high-dimensional cylinder which generalizes the class of monotone twist maps. A solution of a monotone recurrence relation corresponds to an equilibrium of the generalized Frenkel–Kontorova (FK) model. The Aubry–Mather theory for monotone recurrence relations says that for each ω ∈ R there is a Birkhoff minimizer with rotation number ω . Whether all Birkhoff minimizers of rotation number ω form a foliation is a question like whether there is an invariant circle with rotation number ω for a monotone twist map. In this paper we give a criterion for the existence of minimal foliations and study its continuity. The depinning force F d ( ω ) , depending on rotation numbers, is a critical value of the driving force for the FK model, under which there are Birkhoff equilibria and hence the system is pinned, and above which there are no Birkhoff equilibria of rotation number ω and the system is sliding. We show that all Birkhoff minimizers with irrational rotation number ω form a foliation if and only if F d ( ω ) = 0 . If ω = p / q is rational, then F d ( p / q ) = 0 if and only if all ( p , q ) -periodic Birkhoff minimizers constitute a foliation. Moreover, we show that F d ( ω ) is continuous at irrational ω and Hölder continuous at Diophantine points, and it also depends continuously on system parameters. [ABSTRACT FROM AUTHOR]

For a signed cyclic graph G , we can construct a unique virtual link L by taking the medial construction and converting 4-valent vertices of the medial graph to crossings according to the signs. If a virtual link can occur in this way then we say that the virtual link is graphical. In this paper, we shall prove that a virtual link L is graphical if and only if it is checkerboard colorable. On the other hand, we introduce a polynomial F [ G ] for signed cyclic graphs, which is defined via a deletion-marking recursion. We shall establish the relationship between F [ G ] of a signed cyclic graph G and the bracket polynomial of one of the virtual link diagrams associated with G. Finally, we give a spanning subgraph expansion for F [ G ]. [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 quaternary alloy (QA) is simulated on the Bethe lattice (BL) in the form of ABpCqDr and its phase diagrams are calculated by using the exact recursion relations (ERR) for the coordination number z = 3. The QA is designed on the BL by placing A atoms (spin-1/2) on the odd shells and randomly placing B (spin-3/2), C (spin-5/2) or D (spin-1) atoms with probabilities p, q and r, respectively, on the even shells. A compact form of formulation for the QA is obtained in the standard-random approach which can easily be reduced to ternary alloy (TA) and mixed-spin models by the appropriate values of the random variables p, q and r. The phase diagrams are calculated on the temperature and ratio of bilinear interaction parameter planes for given values of probabilities. [ABSTRACT FROM AUTHOR]

A new third-order integrable equation is constructed via combining the recursion operator of the modified KdV equation (MKdV) and its inverse recursion operator. The developed equation will be termed the modified KdV-negative order modified KdV equation (MKdV-nMKdV). The complete integrability of this equation is confirmed by showing that it nicely possesses the Painlevé property. We obtain multiple soliton solutions for the newly developed integrable equation. Moreover, this equation enjoys a variety of solutions which include solitons, peakons, cuspons, negaton, positon, complexiton and other solutions. [ABSTRACT FROM AUTHOR]

We explore the nature of the solution space for the Golomb nested recursion . On this solution space, we define a natural equivalence relation and restrict our attention to non-equivalent solutions. We describe and prove an algorithm that determines whether a given set of initial conditions generates a solution. Up to equivalence, there is a unique solution whose forward differences are eventually either 0 or 1, namely, the Golomb sequence , generated by the initial condition . This sequence is asymptotic to ; we conjecture that this is true of every solution. We further conjecture that each solution has what we call a generational structure that abstracts combinatorial properties of . It appears that for any given solution, its generations are composed of only a finite number of building blocks. [ABSTRACT FROM AUTHOR]

We investigate the time evolution of Hagedorn wavepackets by non-Hermitian quadratic Hamiltonians. We state a direct connection between coherent states and Lagrangian frames. For the time evolution, a multivariate polynomial recursion is derived that describes the activation of lower lying excited states, a phenomenon unprecedented for Hermitian propagation. Finally we apply the propagation of excited states to the Davies–Swanson oscillator. [ABSTRACT FROM AUTHOR]

Multiparametric families of hypergeometric τ-functions of KP or Toda type serve as generating functions for weighted Hurwitz numbers, providing weighted enumerations of branched covers of the Riemann sphere. A graphical interpretation of the weighting is given in terms of constellations mapped onto the covering surface. The theory is placed within the framework of topological recursion, with the Baker function at t = 0 shown to satisfy the quantum spectral curve equation, whose classical limit is rational. A basis for the space of formal power series in the spectral variable is generated that is adapted to the Grassmannian element associated with the τ-function. Multicurrent correlators are defined in terms of the τ-function and shown to provide an alternative generating function for weighted Hurwitz numbers. Fermionic vacuum state expectation value representations are provided for the adapted bases, pair correlators, and multicurrent correlators. Choosing the weight generating function as a polynomial and restricting the number of nonzero “second” KP flow parameters in the Toda τ-function to be finite implies a finite rank covariant derivative equation with rational coefficients satisfied by a finite “window” of adapted basis elements. The pair correlator is shown to provide a Christoffel-Darboux type finite rank integrable kernel, and the WKB series coefficients of the associated adjoint system are computed recursively, leading to topological recursion relations for the generators of the weighted Hurwitz numbers. [ABSTRACT FROM AUTHOR]

The new recently introduced [J. Chem. Phys 102, 7390 (1995)] empirical recursion formula for the scattering solution is here proved to yield an exact polynomial expansion of the operator [E-(H+Γ)]-1, Γ being a simple complex optical potential. The expansion is energy separable and converges uniformly in the real energy domain. The scaling of the Hamiltonian is trivial and does not involve complex analysis. Formal use of the energy-to-time Fourier transform of the ABC (absorbing boundary conditions) Green’s function leads to a recursion polynomial expansion of the ABC time evolution operator that is global in time. Results at any energy and any time can be accumulated simultaneously from a single iterative procedure; no actual Fourier transform is needed since the expansion coefficients are known analytically. The approach can be also used to obtain a perturbation series for the Green’s function. The new iterative methods should be of a great use in the area of the reactive scattering calculations and other related fields. © 1995 American Institute of Physics. [ABSTRACT FROM AUTHOR]

Using a technique based on the hypervirial theorem along with a second quantization formalism, recursion relations for matrix elements and Franck–Condon factors of Morse potentials are obtained. These expressions can be used to calculate recursively matrix elements of the operators qk=(r-re)k, xs=exp[-as(r-re)], dl/dr l, or any combination of them, corresponding to vibrational–rotational states belonging to two distinctly separated Morse oscillators of arbitrary De. The proposed equations give accurate numerical results even when the traditional methods (numerical integration, asymptotic expansions, semiclassical, etc.) present serious inconveniences. The results are valid for any value of the power of the operator and of the quantum numbers v and J of both oscillators. [ABSTRACT FROM AUTHOR]