1,449 results on '"*RECURSION theory"'
Search Results
2. Exact asymptotics and continuous approximations for the Lowest Unique Positive Integer game.
- Author
-
Srinivasan, Arvind and Simon, Burton
- Subjects
- *
NASH equilibrium , *INTEGERS , *DIFFERENTIAL equations , *STOCHASTIC convergence , *GAMES , *RECURSION theory - Abstract
The Lowest Unique Positive Integer game, a.k.a. Limbo, is among the simplest games that can be played by any number of players and has a nontrivial strategic component. Players independently pick positive integers, and the winner is the player that picks the smallest number nobody else picks. The Nash equilibrium for this game is a mixed strategy, (p (1) , p (2) , ...) , where p(k) is the probability you pick k. A recursion for the Nash equilibrium has been previously worked out in the case where the number of players is Poisson distributed, an assumption that can be justified when there is a large pool of potential players. Here, we summarize previous results and prove that as the (expected) number of players, n, goes to infinity, a properly scaled version of the Nash equilibrium random variable converges in distribution to a Unif(0, 1) random variable. The result implies that for large n, players should choose a number uniformly between 1 and ϕ n ∼ O (n / ln (n)) . Convergence to the uniform is rather slow, so we also investigate a continuous analog of the Nash equilibrium using a differential equation derived from the recursion. The resulting approximation is unexpectedly accurate and is interesting in its own right. Studying the differential equation yields some useful analytical results, including a precise expression for ϕ n , and efficient ways to sample from the continuous approximation. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Logic in the deep end.
- Author
-
Leach-Krouse, Graham, Logan, Shay Allen, and Worley, Blane
- Subjects
- *
LOGIC , *SUBSTITUTION (Logic) , *RELEVANCE logic , *AXIOMATIC recursion theory , *RELEVANCE - Abstract
Weak enough relevant logics are often closed under depth substitutions. To determine the breadth of logics with this feature, we show there is a largest sublogic of R closed under depth substitutions and that this logic can be recursively axiomatized. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. Some reflected autoregressive processes with dependencies.
- Author
-
Dimitriou, Ioannis and Fiems, Dieter
- Subjects
- *
GENERATING functions , *RANDOM variables , *QUEUEING networks , *AUTOREGRESSIVE models , *LAPLACE distribution , *RECURSION theory , *BOUNDARY value problems , *ORBITS (Astronomy) - Abstract
Motivated by queueing applications, we study various reflected autoregressive processes with dependencies. Among others, we study cases where the interarrival and service times are proportionally dependent on additive and/or subtracting delay, as well as cases where interarrival times depend on whether the service duration of the previous arrival exceeds or not a random threshold. Moreover, we study cases where the autoregressive parameter is constant as well as a discrete or a continuous random variable. More general dependence structures are also discussed. Our primary aim is to investigate a broad class of recursions of autoregressive type for which several independence assumptions are lifted and for which a detailed exact analysis is provided. We provide expressions for the Laplace transform of the waiting time distribution of a customer in the system in terms of an infinite sum of products of known Laplace transforms. An integer-valued reflected autoregressive process that can be used to model a novel retrial queueing system with impatient customers and a general dependence structure is also considered. For such a model, we provide expressions for the probability generating function of the stationary orbit queue length distribution in terms of an infinite sum of products of known generating functions. A first attempt towards a multidimensional setting is also considered. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
5. The Story of Proof: Logic and the History of Mathematics by John Stillwell: Reviewed by Alexi Block Gorman.
- Author
-
Gorman, Alexi Block
- Subjects
- *
HISTORY of mathematics , *PHILOSOPHY of mathematics , *RECURSION theory , *MATHEMATICAL analysis , *REVERSE mathematics , *MATHEMATICS - Abstract
"The Story of Proof: Logic and the History of Mathematics" by John Stillwell is a book that explores the development of mathematical proofs throughout history. The author examines the emergence of proofs in antiquity and the long-standing dominance of Euclid's foundations of geometry. Stillwell presents a historical narrative of mathematical achievements and subfields, highlighting the ways in which different areas of mathematics are interconnected. The book also discusses the influence of linguistic and conceptual developments on the evolution of mathematics, including the role of infinity and the impact of notation. While the text assumes some prior knowledge of mathematical proofs, it provides numerous examples and explanations to help readers understand the subject. The book concludes with a discussion of modern foundations of mathematics and the potential for computer-assisted proof and automated proof verification. [Extracted from the article]
- Published
- 2024
- Full Text
- View/download PDF
6. Laplace transformations and sine-Gordon type integrable PDE.
- Author
-
Habibullin, I T, Faizulina, K I, and Khakimova, A R
- Subjects
- *
LAPLACE transformation , *LAX pair , *NONLINEAR equations , *SINE-Gordon equation , *RECURSION theory , *LINEAR equations - Abstract
It is well known that the Laplace cascade method is an effective tool for constructing solutions to linear equations of hyperbolic type, as well as nonlinear equations of the Liouville type. The connection between the Laplace method and soliton equations of hyperbolic type remains less studied. The article shows that the Laplace cascade also has important applications in the theory of hyperbolic equations of the soliton type. Laplace's method provides a simple way to construct such fundamental objects related to integrability theory as the recursion operator, the Lax pair and Dubrovin-type equations, allowing one to find algebro-geometric solutions. As an application of this approach, previously unknown recursion operators and Lax pairs are found for two nonlinear integrable equations of the sine-Gordon type. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
7. Solving second-order telegraph equations with high-frequency extrinsic oscillations.
- Author
-
Ait el bhira, H., Kzaz, M., Maach, F., and Zerouaoui, J.
- Subjects
- *
TELEGRAPH & telegraphy , *FREQUENCIES of oscillating systems , *OSCILLATIONS , *EQUATIONS , *RECURSION theory , *ASYMPTOTIC expansions , *PROBLEM solving , *STELLAR oscillations - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
8. Complete Solution of the LSZ Model via Topological Recursion.
- Author
-
Branahl, Johannes and Hock, Alexander
- Subjects
- *
QUANTUM field theory , *RECURSION theory , *DIFFERENCE equations , *COMPLEX matrices , *NONCOMMUTATIVE algebras , *STATISTICAL correlation - Abstract
We prove that the Langmann–Szabo–Zarembo (LSZ) model with quartic potential, a toy model for a quantum field theory on noncommutative spaces grasped as a complex matrix model, obeys topological recursion of Chekhov, Eynard and Orantin. By introducing two families of correlation functions, one corresponding to the meromorphic differentials ω g , n of topological recursion, we obtain Dyson–Schwinger equations that eventually lead to the abstract loop equations being, together with their pole structure, the necessary condition for topological recursion. This strategy to show the exact solvability of the LSZ model establishes another approach towards the exceptional property of integrability in some quantum field theories. We compare differences in the loop equations for the LSZ model (with complex fields) and the Grosse–Wulkenhaar model (with hermitian fields) and their consequences for the resulting particular type of topological recursion that governs the models. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
9. Introduction, Literary Cybernetics: History, Theory, Post-Disciplinarity.
- Author
-
Love, Heather A. and Pao, Lea
- Subjects
- *
CYBERNETICS in literature , *RECURSION theory , *CYBERNETICS , *SYSTEMS theory , *COMPUTATIONAL sociology - Abstract
The article focuses on the intersection of literary studies and cybernetics, highlighting how scholars have increasingly explored cybernetic concepts in literature, including recursion, self-reference, and self-organization. It discusses the interdisciplinary nature of cybernetics and its relevance to understanding literary texts in a systems context.
- Published
- 2023
- Full Text
- View/download PDF
10. The Π21$\Pi ^1_2$ consequences of a theory.
- Author
-
Aguilera, J. P. and Pakhomov, F.
- Subjects
- *
ORDINAL numbers , *RECURSION theory , *PROOF theory , *LINEAR orderings - Abstract
We develop the abstract framework for a proof‐theoretic analysis of theories with scope beyond the ordinal numbers, resulting in an analog of ordinal analysis aimed at the study of theorems of complexity Π21$\Pi ^1_2$. This is done by replacing the use of ordinal numbers by particularly uniform, wellfoundedness preserving functors on the category of linear orders. Generalizing the notion of a proof‐theoretic ordinal, we define the functorial Π21$\Pi ^1_2$ norm of a theory and prove its existence and uniqueness for Π21$\Pi ^1_2$‐sound theories. From this, we further abstract a definition of the Σ21$\Sigma ^1_2$‐ andΠ21$\Pi ^1_2$‐soundness ordinals of a theory; these quantify, respectively, the maximum strength of true Σ21$\Sigma ^1_2$ theorems and minimum strength of false Π21$\Pi ^1_2$ theorems of a given theory. We study these ordinals, developing a proof‐theoretic classification theory for recursively enumerable extensions of ACA0${\mathsf {ACA_0}}$. Using techniques from infinitary and categorical proof theory, generalized recursion theory, constructibility, and forcing, we prove that an admissible ordinal is the Π21$\Pi ^1_2$‐soundness ordinal of some recursively enumerable extension of ACA0${\mathsf {ACA_0}}$ if and only if it is not parameter‐free Σ11$\Sigma ^1_1$‐reflecting. We show that the Σ21$\Sigma ^1_2$‐soundness ordinal of ACA0${\mathsf {ACA_0}}$ is ω1CK$\omega _1^{CK}$ and characterize the Σ21$\Sigma ^1_2$‐soundness ordinals of recursively enumerable, Σ21$\Sigma ^1_2$‐sound extensions of Π11$\Pi ^1_1$‐CA0${\mathsf {CA_0}}$. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
11. Origins of Hierarchical Logical Reasoning.
- Author
-
Dedhe, Abhishek M., Clatterbuck, Hayley, Piantadosi, Steven T., and Cantlon, Jessica F.
- Subjects
- *
THEORY of mind , *COGNITIVE science , *LEARNING , *HUMAN origins , *RECURSION theory - Abstract
Hierarchical cognitive mechanisms underlie sophisticated behaviors, including language, music, mathematics, tool‐use, and theory of mind. The origins of hierarchical logical reasoning have long been, and continue to be, an important puzzle for cognitive science. Prior approaches to hierarchical logical reasoning have often failed to distinguish between observable hierarchical behavior and unobservable hierarchical cognitive mechanisms. Furthermore, past research has been largely methodologically restricted to passive recognition tasks as compared to active generation tasks that are stronger tests of hierarchical rules. We argue that it is necessary to implement learning studies in humans, non‐human species, and machines that are analyzed with formal models comparing the contribution of different cognitive mechanisms implicated in the generation of hierarchical behavior. These studies are critical to advance theories in the domains of recursion, rule‐learning, symbolic reasoning, and the potentially uniquely human cognitive origins of hierarchical logical reasoning. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
12. Evitable iterates of the consistency operator.
- Author
-
Walsh, James
- Subjects
- *
RECURSIVE functions , *RECURSION theory , *PROOF theory , *LOGICAL prediction , *ALGEBRA - Abstract
Why are natural theories pre-well-ordered by consistency strength? In previous work, an approach to this question was proposed. This approach was inspired by Martin's Conjecture, one of the most prominent conjectures in recursion theory. Fixing a reasonable subsystem T of arithmetic, the goal was to classify the recursive functions that are monotone with respect to the Lindenbaum algebra of T. According to an optimistic conjecture, roughly, every such function must be equivalent to an iterate Con T α of the consistency operator "in the limit" within the ultrafilter of sentences that are true in the standard model. In previous work the author established the first case of this optimistic conjecture; roughly, every recursive monotone function is either as weak as the identity operator in the limit or as strong as Con T in the limit. Yet in this note we prove that this optimistic conjecture fails already at the next step; there are recursive monotone functions that are neither as weak as Con T in the limit nor as strong as Con T 2 in the limit. In fact, for every α, we produce a function that is cofinally equivalent to Con T α yet cofinally equivalent to Con T . [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
13. A breakdown in the appropriation of time in adolescence: the futurization disorder.
- Author
-
Valente, Michele
- Subjects
- *
ADOLESCENT psychology , *TIME perspective , *HISTORICAL analysis , *RECURSION theory , *CONNOTATION (Linguistics) - Abstract
This paper proposes a reflection on temporality in adolescence. Particular attention is focused on the process of appropriation of time, which is an operation required of adolescents to allow them to transform time, felt as extraneous to themselves, into a time of their own, that is, a unique and unrepeatable time for that individual. In investigating this process, the author, taking Minolli's concept of historical configuration as a starting point, speculates that adolescents must bring back to themselves a temporality initially configured by the environment. The author also explores the dimension of future as a prospective dimension for the individual. He introduces the idea of going back to one's own future: a process that allows adolescents to transform the future into their own prospect. Finally, the author introduces a clinical vignette to illustrate a particular breakdown in the circular recursion between past, present and future that assumes the connotation of a temporality disorder: the futurization disorder. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
14. Extending properly n-REA sets1.
- Author
-
Cholak, Peter and Gerdes, Peter
- Subjects
- *
COMPUTABLE functions , *RECURSION theory - Abstract
In 1982, Soare and Stob proved that if A is an r.e. set which isn't computable then there is a set of the form A ⊕ W e which isn't of r.e. Turing degree. If we define a properly n + 1 -REA set to be an n + 1 -REA set which isn't Turing equivalent to any n-REA set this result shows that every properly 1-REA set can be extended to a properly 2-REA set. This result was extended by Cholak and Hinman in 1994. They proved that every 2-REA set can be extended to a properly 3-REA set. This leads naturally to the hypothesis that every properly n-REA set can be extended to a properly n + 1 -REA set. Here we show this hypothesis is false and that there is a properly 3-REA set which can't be extended to a properly 4-REA set. Moreover we show this set A can be Δ 2 0 . [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
15. #RecursionFTW.
- Author
-
Ciba, Daniel
- Subjects
- *
DIGITAL technology , *RECURSION theory - Abstract
This essay documents my expansions on a lesson developed in courses that juxtaposed performance and memory studies. Building on a recursive reading of Toni Morrison's literary conceptualisation of rememory, I describe the reiterative nature of memory using two digital performances – a TikTok meme featuring 50 Cent's 'Candy Shop' and a Reddit thread featuring a series of bird paintings. These performances made before the 2020 pandemic show the potentials of collectively inspired art created as virtual media. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
16. Recursion in programs, thought, and language.
- Author
-
Johnson-Laird, P. N., Bucciarelli, Monica, Mackiewicz, Robert, and Khemlani, Sangeet S.
- Subjects
- *
RECURSIVE functions , *RECURSION theory , *KOLMOGOROV complexity , *NATURAL languages , *SHORT-term memory - Abstract
This article presents a theory of recursion in thinking and language. In the logic of computability, a function maps one or more sets to another, and it can have a recursive definition that is semi-circular, i.e., referring in part to the function itself. Any function that is computable – and many are not – can be computed in an infinite number of distinct programs. Some of these programs are semi-circular too, but they needn't be, because repeated loops of instructions can compute any recursive function. Our theory aims to explain how naive individuals devise informal programs in natural language, and is itself implemented in a computer program that creates programs. Participants in our experiments spontaneously simulate loops of instructions in kinematic mental models. They rely on such loops to compute recursive functions for rearranging the order of cars in trains on a track with a siding. Kolmogorov complexity predicts the relative difficulty of abducing such programs – for easy rearrangements, such as reversing the order of the cars, to difficult ones, such as splitting a train in two and interleaving the two resulting halves (equivalent to a faro shuffle). This rearrangement uses both the siding and part of the track as working memories, shuffling cars between them, and so it relies on the power of a linear-bounded computer. Linguistic evidence implies that this power is more than necessary to compose the meanings of sentences in natural language from those of their grammatical constituents. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
17. Computation and Hypercomputation.
- Author
-
Powell, Andrew
- Subjects
- *
TURING machines , *SET theory , *RECURSION theory , *MODEL theory , *PARALLEL computers - Abstract
This paper shows some of the differences and similarities between computation and hypercomputation, the similarities relating to the complexity of propositional computation and the differences being the propositions that can be decided computationally or hypercomputationally. The methods used are ordinal Turing machines with infinitely long programs and diagonalization out of computing complexity classes. The main results are the characterization of inequalities of run time complexities of serial, indeterministic serial and parallel computers and hypercomputers and the specification of a hierarchy of hypercomputers that can hypercompute the truths of all propositions in the standard class model of set theory, the von Neumann hierarchy of pure sets. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
18. Against sedentary school environment: Rethinking the aims of education through physical education.
- Author
-
Leiss, Jodie and Kim, Jeong-Hee
- Subjects
- *
SCHOOL environment , *PHYSICAL activity , *RECURSION theory , *PHYSICAL education , *EDUCATIONAL programs , *ELEMENTARY schools - Abstract
Physical activity is essential for children's current and future health, but most do not get their recommended daily 60 minutes of moderate to vigorous physical activity. Schools are an ideal environment for physical activity since students spend most of their waking hours at school. In this paper, we inquire into a sedentary school environment and its collateral impact on student learning in light of the school experience of Hannah. Grounded in Merleau-Ponty's theory of body and embodiment and Dewey's theory of experience in education, the purpose of this narrative inquiry is to challenge an increasingly sedentary environment that undermines the role of body, hence providing a mis-educative experience. In so doing, we intend to raise awareness of the collateral impact of sedentary education on students and rethink the aims of education for the 21st century to foster the child as a whole embodied being. We suggest three aims of education: first, health as the foundation to develop the whole child; second, adding the fifth R, Rhythm, to Doll's four R's of richness, recursion, relation, and rigor; and finally, understanding what it means to be physically literate. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
19. An inside/outside Ramsey theorem and recursion theory.
- Author
-
Fiori-Carones, Marta, Shafer, Paul, and Soldà, Giovanni
- Subjects
- *
RECURSION theory , *REVERSE mathematics , *RAMSEY numbers , *COMPUTABLE functions , *RAMSEY theory , *SAND - Abstract
Inspired by Ramsey's theorem for pairs, Rival and Sands proved what we refer to as an inside/outside Ramsey theorem : every infinite graph G contains an infinite subset H such that every vertex of G is adjacent to precisely none, one, or infinitely many vertices of H. We analyze the Rival–Sands theorem from the perspective of reverse mathematics and the Weihrauch degrees. In reverse mathematics, we find that the Rival–Sands theorem is equivalent to arithmetical comprehension and hence is stronger than Ramsey's theorem for pairs. We also identify a weak form of the Rival–Sands theorem that is equivalent to Ramsey's theorem for pairs. We turn to the Weihrauch degrees to give a finer analysis of the Rival–Sands theorem's computational strength. We find that the Rival–Sands theorem is Weihrauch equivalent to the double jump of weak König's lemma. We believe that the Rival–Sands theorem is the first natural theorem shown to exhibit exactly this strength. Furthermore, by combining our result with a result of Brattka and Rakotoniaina, we obtain that solving one instance of the Rival–Sands theorem exactly corresponds to simultaneously solving countably many instances of Ramsey's theorem for pairs. Finally, we show that the uniform computational strength of the weak Rival–Sands theorem is weaker than that of Ramsey's theorem for pairs by showing that a number of well-known consequences of Ramsey's theorem for pairs do not Weihrauch reduce to the weak Rival–Sands theorem. We also address an apparent gap in the literature concerning the relationship between Weihrauch degrees corresponding to the ascending/descending sequence principle and the infinite pigeonhole principle. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
20. Computable Reducibility of Metrics on the Reals.
- Author
-
Kornev, R. A.
- Subjects
- *
MATHEMATICAL logic , *COMPUTABLE functions , *RECURSION theory , *METRIC spaces , *BAIRE spaces , *BOOLEAN algebra - Published
- 2022
- Full Text
- View/download PDF
21. The Σ2 theory of Dh(⩽hO) as an uppersemilattice with least and greatest element is decidable.
- Author
-
Barnes, James
- Subjects
- *
TOPOLOGICAL degree , *RECURSION theory - Abstract
The decidability of the two quantifier theory of the hyperarithmetic degrees below Kleene's O in the language of uppersemilattices with least and greatest element is established. This requires a new kind of initial segment result and a new extension of embeddings result both in the hyperarithmetic setting. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
22. MHV amplitudes and BCFW recursion for Yang-Mills theory in the de Sitter static patch.
- Author
-
Albrychiewicz, Emil, Neiman, Yasha, and Tsulaia, Mirian
- Subjects
- *
RECURSION theory , *YANG-Mills theory , *SCATTERING amplitude (Physics) , *SPACE-time symmetries , *INFINITY (Mathematics) - Abstract
We study the scattering problem in the static patch of de Sitter space, i.e. the problem of field evolution between the past and future horizons of a de Sitter observer. We formulate the problem in terms of off-shell fields in Poincare coordinates. This is especially convenient for conformal theories, where the static patch can be viewed as a flat causal diamond, with one tip at the origin and the other at timelike infinity. As an important example, we consider Yang-Mills theory at tree level. We find that static-patch scattering for Yang-Mills is subject to BCFW-like recursion relations. These can reduce any static-patch amplitude to one with N−1MHV helicity structure, dressed by ordinary Minkowski amplitudes. We derive all the N−1MHV static-patch amplitudes from self-dual Yang-Mills field solutions. Using the recursion relations, we then derive from these an infinite set of MHV amplitudes, with arbitrary number of external legs. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
23. A multiplicative version of the Lindley recursion.
- Author
-
Boxma, Onno, Löpker, Andreas, Mandjes, Michel, and Palmowski, Zbigniew
- Subjects
- *
STOCHASTIC analysis , *AUTOREGRESSIVE models , *RECURSION theory , *BOUNDARY value problems , *ORDER picking systems , *PROBABILITY theory , *RANDOM variables - Abstract
This paper presents an analysis of the stochastic recursion W i + 1 = [ V i W i + Y i ] + that can be interpreted as an autoregressive process of order 1, reflected at 0. We start our exposition by a discussion of the model's stability condition. Writing Y i = B i - A i , for independent sequences of nonnegative i.i.d. random variables { A i } i ∈ N 0 and { B i } i ∈ N 0 , and assuming { V i } i ∈ N 0 is an i.i.d. sequence as well (independent of { A i } i ∈ N 0 and { B i } i ∈ N 0 ), we then consider three special cases (i) V i equals a positive value a with certain probability p ∈ (0 , 1) and is negative otherwise, and both A i and B i have a rational LST, (ii) V i attains negative values only and B i has a rational LST, (iii) V i is uniformly distributed on [0, 1], and A i is exponentially distributed. In all three cases, we derive transient and stationary results, where the transient results are in terms of the transform at a geometrically distributed epoch. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
24. Two-point generalized Hermite interpolation: Double-weight function and functional recursion methods for solving nonlinear equations.
- Author
-
Liu, Dongjie and Liu, Chein-Shan
- Subjects
- *
INTERPOLATION , *NEWTON-Raphson method , *RECURSION theory , *RECURSIVE functions - Abstract
Based on the two-point Hermite interpolation technique, the paper proposes a two-point generalized Hermite interpolation and its inversion in terms of weight functions. We prove that upon combining fourth-order optimal iterative scheme to the double Newton's method (DNM), we can yield a generalized Hermite interpolation formula to relate the first-order derivatives at two points, and the converse is also true. Resorted on the DNM and the derived formula for the generalized inverse Hermite interpolation, some new third-order iterative schemes of quadrature type are constructed. Then, the fourth-order optimal iterative schemes are devised by using a double-weight function. A functional recursion formula is developed which can generate a sequence of two-point generalized Hermite interpolations for any two given weight functions with certain constraints; hence, a more general class of fourth-order optimal iterative schemes is developed from the functional recursion formula. The constructions of fourth-order optimal iterative schemes by using the techniques of double-weight function and the recursion formula obtained from a single weight function are appeared in the literature at the first time. The novelties involve deriving a two-point generalized Hermite interpolation and its inversion in terms of weight functions subjected to two conditions and through the recursion formula, relating the DNM to the third-order iterative schemes by the inverse Hermite interpolation, formulating a functional recursion formula, deriving a broad class fourth-order optimal iterative schemes through double-weight functions rather than the previous technique with a single-weight function, and finding that the new double-weight function and the newly developed fourth-order optimal iterative schemes are inclusive being convergent faster and competitive to other iterative schemes. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
25. A simple extrapolation of thermodynamic perturbation theory to infinite order.
- Author
-
Ghobadi, Ahmadreza F. and Elliott, J. Richard
- Subjects
- *
EXTRAPOLATION , *THERMODYNAMICS , *QUANTUM perturbations , *INFINITY (Mathematics) , *RECURSION theory - Abstract
Recent analyses of the third and fourth order perturbation contributions to the equations of state for square well spheres and Lennard-Jones chains show trends that persist across orders and molecular models. In particular, the ratio between orders (e.g., A3/A2, where Ai is the ith order perturbation contribution) exhibits a peak when plotted with respect to density. The trend resembles a Gaussian curve with the peak near the critical density. This observation can form the basis for a simple recursion and extrapolation from the highest available order to infinite order. The resulting extrapolation is analytic and therefore cannot fully characterize the critical region, but it remarkably improves accuracy, especially for the binodal curve. Whereas a second order theory is typically accurate for the binodal at temperatures within 90% of the critical temperature, the extrapolated result is accurate to within 99% of the critical temperature. In addition to square well spheres and Lennard-Jones chains, we demonstrate how the method can be applied semi-empirically to the Perturbed Chain - Statistical Associating Fluid Theory (PC-SAFT). [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
26. The Shortest Duration Constrained Hidden Markov Model: Data denoise and forecast optimization on the country-product matrix for the Fitness-Complexity Algorithm.
- Author
-
Song, Pengcheng, Zong, Xiangyu, Chen, Ximing, Zhao, Qin, and Guo, Lubingzhi
- Subjects
- *
HIDDEN Markov models , *DIVERSIFICATION in industry , *RECURSION theory , *ALGORITHMS , *ECONOMIC indicators , *DATA modeling , *NATIONAL competency-based educational tests - Abstract
The Economic Fitness Index describes industrial completeness and comprehensively reflects product diversification with competitiveness and product complexity in production globalization. The Fitness-Complexity Algorithm offers a scientific approach to predicting GDP and obtains fruitful results. As a recursion algorithm, the non-linear iteration processes give novel insights into product complexity and country fitness without noise data. However, the Country-Product Matrix and Revealed Comparative Advantage data have abnormal noises which contradict the relative stability of product diversity and the transformation of global production. The data noise entering the iteration algorithm, combined with positively related Fitness and Complexity, will be amplified in each recursion step. We introduce the Shortest Duration Constrained Hidden Markov Model (SDC-HMM) to denoise the Country-Product Matrix for the first time. After the country-product matrix test, the country case test, the noise estimation test and the panel regression test of national economic fitness indicators to predict GDP growth, we show that the SDC-HMM could reduce abnormal noise by about 25% and identify change points. This article provides intra-sample predictions that theoretically confirm that the SDC-HMM can improve the effectiveness of economic fitness indicators in interpreting economic growth. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
27. Risk sensitivity and theory of mind in human coordination.
- Author
-
Ferreira, Pedro L., Santos, Francisco C., and Pequito, Sérgio
- Subjects
- *
THEORY of mind , *PROSPECT theory , *CAPACITY requirements planning , *RECURSION theory , *HUMAN beings - Abstract
What humans do when exposed to uncertainty, incomplete information, and a dynamic environment influenced by other agents remains an open scientific challenge with important implications in both science and engineering applications. In these contexts, humans handle social situations by employing elaborate cognitive mechanisms such as theory of mind and risk sensitivity. Here we resort to a novel theoretical model, showing that both mechanisms leverage coordinated behaviors among self-regarding individuals. Particularly, we resort to cumulative prospect theory and level-k recursions to show how biases towards optimism and the capacity of planning ahead significantly increase coordinated, cooperative action. These results suggest that the reason why humans are good at coordination may stem from the fact that we are cognitively biased to do so. Author summary: We propose a new computational model characterizing coordination among self-regarding individuals under theory of mind and risk sensitivity. Theory of mind enables decision-making based on the attribution of beliefs, knowledge, or goals to others, whereas different risk sensitivities allows one to assess the impact of different ways of valuing uncertain returns, as captured by descriptive theories from social-economic studies. Together they provide evidence that biases towards optimism, and the capacity for planning ahead, significantly increase coordinated, cooperative action. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
28. Duality of positive and negative integrable hierarchies via relativistically invariant fields.
- Author
-
Lou, S. Y., Hu, X. B., and Liu, Q. P.
- Subjects
- *
RECURSION theory , *OPERATOR equations , *KLEIN-Gordon equation , *SINE-Gordon equation , *SPACE-time symmetries , *SYMMETRY - Abstract
It is shown that the relativistic invariance plays a key role in the study of integrable systems. Using the relativistically invariant sine-Gordon equation, the Tzitzeica equation, the Toda fields and the second heavenly equation as dual relations, some continuous and discrete integrable positive hierarchies such as the potential modified Korteweg-de Vries hierarchy, the potential Fordy-Gibbons hierarchies, the potential dispersionless Kadomtsev-Petviashvili-like (dKPL) hierarchy, the differential-difference dKPL hierarchy and the second heavenly hierarchies are converted to the integrable negative hierarchies including the sG hierarchy and the Tzitzeica hierarchy, the two-dimensional dispersionless Toda hierarchy, the two-dimensional Toda hierarchies and negative heavenly hierarchy. In (1+1)-dimensional cases the positive/negative hierarchy dualities are guaranteed by the dualities between the recursion operators and their inverses. In (2+1)-dimensional cases, the positive/negative hierarchy dualities are explicitly shown by using the formal series symmetry approach, the mastersymmetry method and the relativistic invariance of the duality relations. For the 4-dimensional heavenly system, the duality problem is studied firstly by formal series symmetry approach. Two elegant commuting recursion operators of the heavenly equation appear naturally from the formal series symmetry approach so that the duality problem can also be studied by means of the recursion operators. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
29. On Short Expressions for Cosets of Permutation Subgroups.
- Author
-
Dona, Daniele
- Subjects
- *
LINEAR algebraic groups , *PERMUTATIONS , *ISOMORPHISM (Mathematics) , *RECURSION theory - Abstract
Following Babai's algorithm (Graph isomorphism in quasipolynomial time, arXiv:1512.03547v2, 2016) for the string isomorphism problem, we determine that it is possible to write expressions of short length describing certain permutation cosets, including all permutation subgroups. This is feasible both in the original version of the algorithm and in its CFSG-free version, by Babai (2016, §13.1) and Pyber (A CFSG-free analysis of Babai's quasipolynomial GI algorithm, arXiv:1605.08266, 2016). The existence of such descriptions gives a weak form of the Cameron–Maróti classification, even without assuming CFSG. This is applicable to proofs of diameter bounds for Alt (n) as in Helfgott (Growth in linear algebraic groups and permutation groups: towards a unified perspective, arXiv:1804.03049, 2018): our main result is used in Dona (Towards a CFSG-free diameter bound for Alt (n) , arXiv:1810.02710v3, 2018) to free Helfgott's proof from the use of CFSG. We also thoroughly explicate Babai's recursion process (as given in Helfgott et al. in Graph isomorphisms in quasi-polynomial time, arXiv:1710.04574, 2017) and obtain explicit constants for the runtime of the algorithm, both with and without the use of CFSG. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
30. Incomplete block‐matrix factorization of M‐matrices using two‐step iterative method for matrix inversion and preconditioning.
- Author
-
Buranay, S.C. and Iyikal, O.C.
- Subjects
- *
MATRIX inversion , *LAPLACE'S equation , *FACTORIZATION , *BOUNDARY value problems , *FINITE difference method , *RECURSION theory - Abstract
Using the general method of Owe Axelsson given in 1986 for incomplete factorization of M‐matrices in block‐matrix form, we give a recursive approach to construct incomplete block‐matrix factorization of M‐matrices by proposing a two‐step iterative method for the approximation of the inverse of diagonal pivoting block matrices at each stage of the recursion. For various predescribed tolerances in the accuracy of the approximation of the inverses, the obtained incomplete block‐matrix factorizations are used to precondition the iterative methods as one‐step stationary iterative (OSSI) method and biconjugate gradient stabilized method (BI‐CGSTAB). Certain applications are conducted on M‐matrices occurring from the discretization of two Dirichlet boundary value problems of Laplace's equation on a rectangle using finite difference method. Numerical results justify that the given incomplete block‐matrix factorization of M‐matrices using the two‐step iterative method to approximate the inverse of diagonal pivoting block matrices at each stage of the recursion give robust preconditioners. The obtained results are presented through tables and figures. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
31. Learning theory in the arithmetic hierarchy II.
- Author
-
Beros, Achilles A., Beros, Konstantinos A., Flores, Daniel, Gaffar, Umar, Webb, David J., and Yoon, Soowhan
- Subjects
- *
ARITHMETIC , *COMPUTABLE functions , *RECURSION theory - Abstract
The present work determines the arithmetic complexity of the index sets of u.c.e. families which are learnable according to various criteria of algorithmic learning. Specifically, we prove that the index set of codes for families that are TxtFex b a -learnable is Σ 4 0 -complete and that the index set of TxtFex ∗ ∗ -learnable and the index set of TxtFext ∗ ∗ -learnable families are both Σ 5 0 -complete. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
32. Multi prime numbers principle to expand implementation of CRT method on RSA algorithm.
- Author
-
Hermawan, Nanang Triagung Edi, Winarko, Edi, Ashari, Ahmad, Meiliasari, Meiliasari, Rahmawati, Yuli, Delina, Mutia, and Fitriani, Ella
- Subjects
- *
PRIME numbers , *CHINESE remainder theorem , *RSA algorithm , *IMAGE encryption , *PROBLEM solving , *RECURSION theory - Abstract
One of the uses of the Chinese Remainder Theorem (CRT) is to shorten the time in the RSA Cryptosystem decryption process. However, in applying a combination of the CRT method and the RSA Algorithm with Python programming modules, recursion errors often occurred when determining the inverse modulus to establish the private key. The error was caused by limitation iterations of the related algorithm. Some Python library needs more iteration processes to calculate the inverse modulus for larger key size. This is a pure computational problem. The standard RSA algorithm uses two prime numbers to generate their key pairs. The multi-prime RSA modification based on more than two prime numbers can be applied to solve the problem. A modified RSA was applied in Python programming that generates keys based on 2, 4, 8, 16, and 32 prime numbers. Regarding on our experiments, the combination of the CRT method and RSA algorithm based on four prime numbers can be applied without recursion error up to a key length of 6280 bits, with eight primes up to 12,560 bits, with sixteen primes up to 25,120 bits, and with thirty-two primes up to 50,240 bits. Implementation of more multi-prime numbers can expand to combine the CRT method and RSA Algorithm for longer key sizes by approximation relation y = 1567,8x + 63,333, which y is the key size and x is the number of primes numbers. The method also can increase key generation and decryption rate significantly. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
33. Recursive Variable Projection Algorithm for a Class of Separable Nonlinear Models.
- Author
-
Gan, Min, Guan, Yu, Chen, Guang-Yong, and Chen, C. L. Philip
- Subjects
- *
ALGORITHMS , *SIGNAL processing , *SYSTEM identification , *PARAMETER estimation , *MACHINE learning , *RECURSION theory - Abstract
In this article, we study the recursive algorithms for a class of separable nonlinear models (SNLMs) in which the parameters can be partitioned into a linear part and a nonlinear part. Such models are very common in machine learning, system identification, and signal processing. Utilizing the special structure of the SNLMs, we propose a recursive variable projection (RVP) algorithm, in which at each recursion, the linear parameters of the model are eliminated, and the nonlinear parameters are updated by the recursive Levenberg–Marquart algorithm. Then, based on the updated nonlinear parameters, the linear parameters are updated by the recursive least-squares algorithm. According to a convergence analysis of the RVP algorithm, the parameter estimation error is mean-square bounded. Numerical examples confirm the satisfactory performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
34. Forms of Solutions for Some Two-Dimensional Systems of Rational Partial Recursion Equations.
- Author
-
Ibrahim, Tarek F. and Khan, A. Q.
- Subjects
- *
DIFFERENCE equations , *MATHEMATICAL induction , *EQUATIONS , *RECURSION theory , *REACTION-diffusion equations - Abstract
In this paper, we offer the closed-form expressions of systems of second-order partial difference equations. We will utilize an alternative approach to verify the results by (odd-even) dual mathematical induction. We research and enforce the specific solutions of partial difference formulas and ordinary difference formulas as a straight effect. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
35. On topological recursion for Wilson loops in N = 4 SYM at strong coupling.
- Author
-
Beccaria, M. and Hasan, A.
- Subjects
- *
YANG-Mills theory , *CORRELATORS , *COUPLES , *RECURSION theory - Abstract
We consider U(N) N = 4 super Yang-Mills theory and discuss how to extract the strong coupling limit of non-planar corrections to observables involving the 1 2 -BPS Wilson loop. Our approach is based on a suitable saddle point treatment of the Eynard-Orantin topological recursion in the Gaussian matrix model. Working directly at strong coupling we avoid the usual procedure of first computing observables at finite planar coupling λ, order by order in 1/N, and then taking the λ ≫ 1 limit. In the proposed approach, matrix model multi-point resolvents take a simplified form and some structures of the genus expansion, hardly visible at low order, may be identified and rigorously proved. As a sample application, we consider the expectation value of multiple coincident circular supersymmetric Wilson loops as well as their correlator with single trace chiral operators. For these quantities we provide novel results about the structure of their genus expansion at large tension, generalising recent results in arXiv:2011.02885. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
36. Turing degrees in Polish spaces and decomposability of Borel functions.
- Author
-
Gregoriades, Vassilios, Kihara, Takayuki, and Ng, Keng Meng
- Subjects
- *
BOREL sets , *RECURSION theory , *ANALYTIC functions , *SET theory , *SPACE , *LOGICAL prediction - Abstract
We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore–Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
37. Dynamic structural models with covariates for short-term forecasting of time series with complex seasonal patterns.
- Author
-
Puindi, António Casimiro and Silva, Maria Eduarda
- Subjects
- *
STRUCTURAL models , *FORECASTING , *DYNAMIC models , *MAXIMUM likelihood statistics , *KALMAN filtering , *RECURSION theory - Abstract
This work presents a framework of dynamic structural models with covariates for short-term forecasting of time series with complex seasonal patterns. The framework is based on the multiple sources of randomness formulation. A noise model is formulated to allow the incorporation of randomness into the seasonal component and to propagate this same randomness in the coefficients of the variant trigonometric terms over time. A unique, recursive and systematic computational procedure based on the maximum likelihood estimation under the hypothesis of Gaussian errors is introduced. The referred procedure combines the Kalman filter with recursive adjustment of the covariance matrices and the selection method of harmonics number in the trigonometric terms. A key feature of this method is that it allows estimating not only the states of the system but also allows obtaining the standard errors of the estimated parameters and the prediction intervals. In addition, this work also presents a non-parametric bootstrap approach to improve the forecasting method based on Kalman filter recursions. The proposed framework is empirically explored with two real time series. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
38. Joint Eigenfunctions for the Relativistic Calogero–Moser Hamiltonians of Hyperbolic Type. III. Factorized Asymptotics.
- Author
-
Hallnäs, Martin and Ruijsenaars, Simon
- Subjects
- *
EIGENFUNCTIONS , *RELATIVISTIC particles , *HYPERBOLIC spaces , *RECURSION theory - Abstract
In the two preceding parts of this series of papers, we introduced and studied a recursion scheme for constructing joint eigenfunctions |$J_N(a_+, a_-,b;x,y)$| of the Hamiltonians arising in the integrable |$N$| -particle systems of hyperbolic relativistic Calogero–Moser type. We focused on the 1st steps of the scheme in Part I and on the cases |$N=2$| and |$N=3$| in Part II. In this paper, we determine the dominant asymptotics of a similarity-transformed function |$\textrm{E}_N(b;x,y)$| for |$y_j-y_{j+1}\to \infty $| , |$j=1,\ldots , N-1$| and thereby confirm the long-standing conjecture that the particles in the hyperbolic relativistic Calogero–Moser system exhibit soliton scattering. This result generalizes a main result in Part II to all particle numbers |$N>3$|. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
39. Horizontal and vertical log-concavity.
- Author
-
Heim, Bernhard and Neuhauser, Markus
- Subjects
- *
LAGUERRE polynomials , *GENERATING functions , *NUMBER theory , *BINOMIAL coefficients , *COMBINATORICS , *RECURSION theory - Abstract
Horizontal and vertical generating functions and recursion relations have been investigated by Comtet for triangular double sequences. In this paper we investigate the horizontal and vertical log-concavity of triangular sequences assigned to polynomials which show up in combinatorics, number theory and physics. This includes Laguerre polynomials, the Pochhammer polynomials, the D'Arcais and Nekrasov–Okounkov polynomials. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
40. Fault estimation for discrete time‐variant systems subject to actuator and sensor saturations.
- Author
-
Li, Yueyang, Liu, Shuai, Li, Yibin, and Zhao, Dong
- Subjects
- *
TIME-varying systems , *DISCRETE systems , *ACTUATORS , *BASE pairs , *DETECTORS , *RECURSION theory - Abstract
This article studies the H∞ fault estimation (FE) problem for linear discrete time‐variant systems with actuator and sensor saturations. To handle the saturation nonlinearities for FE problem, a pair of an auxiliary linear model and an associated performance function augmenting from the conventional H∞ performance index are constructed. Based on this pair, the original FE problem is readdressed as a two‐step optimization issue with an indefinite quadratic cost function. For a feasible optimization solution, the partial equivalence between a stationary point for a quadratic optimization problem and a projection for vectors in indefinite inner‐product space is utilized. A Krein‐space based inner product interpretation for the indefinite cost function is established and optimal linear estimation technique is employed to derive the stationary point of the aforementioned indefinite quadratic cost function. The existence condition of the fault estimator is explicitly obtained, and the fault is reconstructed analytically via a forward recursion algorithm. Two examples are given to show the effectiveness of the proposed FE scheme. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
41. A multi-server/single-server duality.
- Author
-
Scheller-Wolf, Alan
- Subjects
- *
QUEUING theory , *RANDOM walks , *RECURSION theory , *MARKOV processes - Abstract
How does load and the notion of I spare servers i (see [[8]]) affect the dependence structure of HT ht ? How can we describe the dependence structure this induces on HT ht ? The study of multi-server queues (with HT ht servers) is complicated by the need to track and analyze a I k i -dimensional vector to precisely characterize performance. [Extracted from the article]
- Published
- 2022
- Full Text
- View/download PDF
42. Darboux transformation and exact solutions for a (2 + 1)-dimensional integrable system of nonlinear evolution equations.
- Author
-
Zhou, Zhen Chuan and Zhu, Xiao Ming
- Subjects
- *
NONLINEAR evolution equations , *NONLINEAR equations , *DARBOUX transformations , *BASE pairs , *LAX pair , *RECURSION theory - Abstract
In this paper, starting from a spectral problem, we construct a (2 + 1) -dimensional integrable system of nonlinear evolution equations. Based on the Lax pair, the recursion operator and Darboux transformation for the whole hierarchy were constructed. As an application, some exact solutions for the hierarchy are obtained by using the Darboux transformation. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
43. Concentration inequalities for the empirical distribution of discrete distributions: beyond the method of types.
- Author
-
Mardia, Jay, Jiao, Jiantao, Tánczos, Ervin, Nowak, Robert D, and Weissman, Tsachy
- Subjects
- *
DISTRIBUTION (Probability theory) , *SAMPLE size (Statistics) , *MATHEMATICAL equivalence , *RECURSION theory - Abstract
We study concentration inequalities for the Kullback–Leibler (KL) divergence between the empirical distribution and the true distribution. Applying a recursion technique, we improve over the method of types bound uniformly in all regimes of sample size |$n$| and alphabet size |$k$| , and the improvement becomes more significant when |$k$| is large. We discuss the applications of our results in obtaining tighter concentration inequalities for |$L_1$| deviations of the empirical distribution from the true distribution, and the difference between concentration around the expectation or zero. We also obtain asymptotically tight bounds on the variance of the KL divergence between the empirical and true distribution, and demonstrate their quantitatively different behaviours between small and large sample sizes compared to the alphabet size. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
44. Variations of largest rectangle recognition amidst a bichromatic point set.
- Author
-
Acharyya, Ankush, De, Minati, Nandy, Subhas C., and Pandit, Supantha
- Subjects
- *
POINT set theory , *ALGORITHMS , *COMPUTATIONAL geometry , *APPLIED mathematics , *RECTANGLES , *RECURSION theory , *DATA structures - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
45. Inferring Lower Runtime Bounds for Integer Programs.
- Author
-
FROHN, FLORIAN, NAAF, MATTHIAS, BROCKSCHMIDT, MARC, and GIESL, JÜRGEN
- Subjects
- *
SIGNS & symbols , *RECURSION theory , *INTEGERS , *CALCULUS , *KERNEL (Mathematics) - Abstract
We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-recursion. Our technique constructs symbolic representations of program executions using a framework for iterative, under-approximating program simplification. The core of this simplification is a method for (under-approximating) program acceleration based on recurrence solving and a variation of ranking functions. Afterwards, we deduce asymptotic lower bounds from the resulting simplified programs using a special-purpose calculus and an SMT encoding. We implemented our technique in our tool LoAT and show that it infers non-trivial lower bounds for a large class of examples. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
46. Topological recursion and geometry.
- Author
-
Borot, Gaëtan
- Subjects
- *
QUANTUM field theory , *GEOMETRY , *SYMPLECTIC geometry , *RECURSION theory , *TOPOLOGICAL fields - Abstract
This paper aims at explaining some incarnations of the idea of topological recursion: in two-dimensional quantum field theories (2d TQFTs), in cohomological field theories (CohFT), and in the computation of volumes of the moduli space of curves. It gives an introduction to the formalism of quantum Airy structures on which the topological recursion is based, which is seen at work in the above topics. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
47. In Memoriam - Alan Selman (1941 - 2021).
- Subjects
- *
SCHOLARSHIPS , *RECURSION theory , *COMMUNITIES - Abstract
Alan brought several visitors to Buffalo, including Reuven Bar-Yehuda in 1992 and Christian Glaßer, Edith Hemaspaandra, and Mitsu Ogihara as postdocs. B Mitsunori Ogihara b Alan's friends and colleagues Graph With great sadness, we report the passing of Alan L. Selman, who left this world on January 22, 2021. Alan received his Ph.D. in Mathematics in 1970 from the Pennsylvania State University. [Extracted from the article]
- Published
- 2023
- Full Text
- View/download PDF
48. Probabilistic Occupancy via Forward Stochastic Reachability for Markov Jump Affine Systems.
- Author
-
Vinod, Abraham P. and Oishi, Meeko M. K.
- Subjects
- *
MARKOVIAN jump linear systems , *STOCHASTIC control theory , *FOURIER transforms , *ROBOT kinematics , *CONVEX bodies , *RECURSION theory - Abstract
Probabilistic occupancy, the likelihood that the state at a known future time lies in a given set, is important in a variety of stochastic motion planning problems. We provide efficient computational techniques, based in Fourier transforms, to characterize the stochasticity of the future state for Markov jump affine systems. This class of systems captures a variety of important dynamics in planning problems, including the Dubins’ vehicle. We employ convex optimization to compute outer approximations of the superlevel sets of the probabilistic occupancy function, which is a key for preserving the safety guarantees sought in collision-avoidance problems. In contrast to traditional approaches, our approach does not rely on gridding, recursion, or sampling, accommodates non-Gaussian perturbed dynamics, and affords outer-approximation guarantees. We demonstrate our methods on the target pursuit problem with multiple robots pursuing a nonadversarial target with stochastic dynamics, and on the problem of computing keep-out regions for stochastic collision avoidance of a Dubins’ vehicle. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
49. A note on the Drinfeld associator for genus-zero superstring amplitudes in twisted de Rham theory.
- Author
-
Kaderli, André
- Subjects
- *
INTERSECTION numbers , *NUMBER theory , *REPRESENTATIONS of algebras , *LIE algebras , *INTERSECTION theory , *INTERSECTION graph theory , *RECURSION theory - Abstract
The string corrections of tree-level open-string amplitudes can be described by Selberg integrals satisfying a Knizhnik–Zamolodchikov (KZ) equation. This allows for a recursion of the α′-expansion of tree-level string corrections in the number of external states using the Drinfeld associator. While the feasibility of this recursion is well-known, we provide a mathematical description in terms of twisted de Rham theory and intersection numbers of twisted forms. In particular, this leads to purely combinatorial expressions for the matrix representation of the Lie algebra generators appearing in the KZ equation in terms of directed graphs. This, in turn, admits efficient algorithms for symbolic and numerical computations using adjacency matrices of directed graphs and is a crucial step towards analogous recursions and algorithms at higher genera. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
50. Boundary contributions of on-shell recursion relations with multiple-line deformation.
- Author
-
Hu, Chang, Li, Xiao-Di, and Li, Yi
- Subjects
- *
QUANTUM field theory , *RECURSION theory - Abstract
The on-shell recursion relation has been recognized as a powerful tool for calculating tree-level amplitudes in quantum field theory, but it does not work well when the residue of the deformed amplitude A ^ (z) does not vanish at infinity of z. However, in such a situation, we still can get the right amplitude by computing the boundary contribution explicitly. In Arkani-Hamed and Kaplan (JHEP 04:076. 10.1088/1126-6708/2008/04/076. arXiv:0801.2385, 2008), the background field method was first used to analyze the boundary behaviors of amplitudes with two deformed external lines in different theories. The same method has been generalized to calculate the explicit boundary operators of some amplitudes with BCFW-like deformation in Jin and Feng (JHEP 04:123. 10.1007/JHEP04(2016)123. arXiv:1507.00463, 2016). In this paper, we will take a step further to generalize the method to the case of multiple-line deformation, and to show how the boundary behaviors (even the boundary contributions) can be extracted in the method. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.