37 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. 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
25. 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
26. 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
27. 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
28. 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
29. A universal algorithm for Krull's theorem.
- Author
-
Powell, Thomas, Schuster, Peter, and Wiesnet, Franziskus
- Subjects
- *
PROOF theory , *PRIME ideals , *ALGORITHMS , *ALGEBRA , *VALUATION , *RECURSION theory - Abstract
We give a computational interpretation to an abstract formulation of Krull's theorem, by analysing its classical proof based on Zorn's lemma. Our approach is inspired by proof theory, and uses a form of update recursion to replace the existence of maximal ideals. Our main result allows us to derive, in a uniform way, algorithms which compute witnesses for existential theorems in countable abstract algebra. We give a number of concrete examples of this phenomenon, including the prime ideal theorem and Krull's theorem on valuation rings. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
30. A hierarchical layout approach for underfloor heating systems in single-family residential buildings.
- Author
-
Shi, Ganquan, Qiu, Andong, and Yang, Zhouwang
- Subjects
- *
RESIDENTIAL heating systems , *DWELLINGS , *HEATING , *RECTANGLES , *ENERGY consumption , *RECURSION theory - Abstract
[Display omitted] • A hierarchical approach for automatic layout of an underfloor heating system is proposed. • The routing problem is formulated as a shortest path problem in a proper routing graph. • An order relation is defined to separate the intersecting paths. • A depth-first layout algorithm based on recursion is developed to solve the coverage path planning problem. The layout of an underfloor heating system determines its heating performance. Conventionally, the design is completed by qualified experts using professional software, but this method is inefficient and heavily relies on the experts' previous experience. This paper proposes a hierarchical approach for the automatic design of underfloor heating systems aimed at residential buildings, and the underfloor heating layout problem is decomposed into a routing problem and coverage path planning problem. First, the routing problem is formulated as a shortest path problem in an appropriate routing graph and solved to provide the routing of pipes for further coverage. Subsequently, a depth-first layout algorithm is developed to recursively simplify the coverage path planning problem to obtain the basic rectangle layout, achieving uniform coverage of the given layout zone. Simulation results on two houses show that, unlike one popular commercial platform, the proposed approach generated feasible solutions in all 13 test instances. The new method improved the minimum temperature, average temperature, average percentage of nodes greater than 30 °C, and total energy efficiency by 3.18 °C, 0.79 °C, 3.23%, and 4.19%, respectively, with a lower variance on average. These improvements lead to a higher coverage rate, more even thermal distribution, and stronger robustness under flexible parameter selection. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
31. A novel constrained UKF method for both updating structural parameters and identifying excitations for nonlinear structures.
- Author
-
Li, Xingyu, Zhang, Chaodong, Zheng, Yue, and Zhang, Ning
- Subjects
- *
RECURSION theory , *KALMAN filtering , *GROUND motion , *RANDOM walks , *REINFORCED concrete , *STEEL framing - Abstract
Finite element-based model updating of civil structures has been attracting increasing attention in structural health assessment and fragility analysis since several decades ago. However, the previously proposed finite element (FE) model updating methods for structures are either primarily limit to linear models under given external excitation or unknown excitation which should satisfy some assumptions. In this regard, this study proposes a novel constrained unscented Kalman filter (UKF) method for both updating structural parameters and identifying unknown external excitations without any assumption for strongly nonlinear structures. The unknown excitation (e.g., ground acceleration) can be preliminarily extracted from the state and measurement equations and then can be estimated by a recursive nonlinear least-square algorithm. To implement the recursive nonlinear least-square algorithm, a combined Matlab-OpenSees recursion platform herein is specially developed. It should be noted that certain constraints are necessary to be imposed on the sigma points to guarantee the propagation of the sigma points at each recursion step when the recursive nonlinear least-square algorithm is running. A three-story three-span steel frame and a three-span continuous reinforced concrete (RC) bridge, as two examples, are investigated for verifying the applicability of the novel constrained UKF method. The parameters which are most sensitive to the dynamic responses of structures are determined for identification. Subsequently, these structural parameters and the unknown excitation (e.g., ground motion) are jointly identified using the novel constrained UKF method based on partially measured noise-contaminated responses. In such a way, the feasibility of the Matlab-OpenSees recursion platform for structural dynamic inverse problems and the effectiveness of the novel constrained UKF for nonlinear model updating of structures are both verified. • A novel constrained unscented Kalman filter (UKF) with unknown input is proposed and its concise framework is presented for both updating structural parameters and identifying excitations for nonlinear structures. • The identification of unknown excitation without dependence of any assumption such as random walk model. • A combined Matlab-OpenSees recursion platform is developed for implementing the novel constrained UKF method. • The novel UKF method can be applied to complex civil structures with strong nonlinearities. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
32. Hidden Markov Model and multifractal method-based predictive quantization complexity models vis-á-vis the differential prognosis and differentiation of Multiple Sclerosis' subgroups.
- Author
-
Karaca, Yeliz, Baleanu, Dumitru, and Karabudak, Rana
- Subjects
- *
MARKOV processes , *FORWARD-backward algorithm , *MULTIPLE sclerosis , *VITERBI decoding , *APPLIED sciences , *RECURSION theory , *PROGNOSIS - Abstract
Hidden Markov Model (HMM) is a stochastic process where implicit or latent stochastic processes can be inferred indirectly through a sequence of observed states. HMM as a mathematical model for uncertain phenomena is applicable for the description and computation of complex dynamical behaviours enabling the mathematical formulation of neural dynamics across spatial and temporal scales. The human brain with its fractal structure demonstrates complex dynamics and fractals in the brain are characterized by irregularity, singularity and self-similarity in terms of form at different observation levels, making detection difficult as observations in real-time occurrences can be time variant, discrete, continuous or noisy. Multiple Sclerosis (MS) is an autoimmune degenerative disease with time and space related dissemination, leading to neuronal apoptosis, coupled with some subtle features that could be overlooked by physicians. This study, through the proposed integrated approach with multi-source complex spatial data, aims to attain accurate prediction, diagnosis and prognosis of MS subgroups by HMM with Viterbi algorithm and Forward–Backward algorithm as the dynamic and efficient products of knowledge-based and Artificial Intelligence (AI)-based systems within the framework of precision medicine. Multifractal Bayesian method (MFM) accordingly applied to identify and eliminate "insignificant" irregularities while maintaining "significant" singularities. An efficient modelling of HMM is proposed to diagnose and predict the course of MS while using MFM method. Unlike the methods employed in previous studies, our proposed integrated novel method encompasses the subsequent approaches based on reliable MS dataset (X) collected: (i) MFM method was applied (X) to MS dataset to characterize the irregular, self-similar and significant attributes, thus, attributes with "insignificant" irregularities were eliminated and "significant" singularities were maintained. MFM-MS dataset (X ˆ) was generated. (ii) The continuous values in the MS dataset (X) and MFM-MS dataset (X ˆ) were converted into discrete values through vector quantization method of the HMM (iii) Through transitional matrices, different observation matrices were computed from the both datasets. (v) Computational complexity has been computed for both datasets. (vi) The results of the HMM models based on observation matrices obtained from both datasets were compared. In terms of the integrated HMM model proposed and the MS dataset handled, no earlier work exists in the literature. The experimental results demonstrate the applicability and accuracy of our novel proposed integrated method, HMM and Multifractal (HMM-MFM) method, for the application to the MS dataset (X). Compared with conventional methods, our novel method has achieved more superiority regarding extracting subtle and hidden details, which are significant for distinguishing different dynamic and complex systems including engineering and other related applied sciences. Thus, we have aimed at pointing a new frontier by providing a novel alternative mathematical model to facilitate the critical decision-making, management and prediction processes among the related areas in chaotic, dynamic complex systems with intricate and transient states. • Novel HMM-MFM model reveals critical significance of predictive quantization in dynamic complexity. • Predictive quantization by HMM-MFM model for dynamic and transient states in varying complex systems. • Viterbi algorithm's recursion enables maximization and uncovering of the most probable hidden state sequence. • Computational complexity and reliability of Forward–Backward procedure, guaranteeing local maxima and maximizing the objective function φ (N 2 T). • Multifarious knowledge-based approach with a facilitating function in precision medicine ensuring personalized treatment tailoring. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
33. A characterization of [formula omitted]-reflecting ordinals.
- Author
-
Aguilera, J.P.
- Subjects
- *
RECURSION theory , *SET theory - Abstract
We consider clopen game formulae , analogous to the open game formulae widely studied in admissible recursion theory. This leads to characterizing the locally countable Σ 1 1 -reflecting ordinals α as those for which, over L α , the clopen-game–definable relations are not precisely those which are both open-game and closed-game definable. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
34. On-shell recursion relations for nonrelativistic effective field theories.
- Author
-
Mojahed, Martin A. and Brauner, Tomáš
- Subjects
- *
DISPERSION relations , *SCATTERING amplitude (Physics) , *RECURSION theory - Abstract
We derive on-shell recursion relations for nonrelativistic effective field theories (EFTs) with enhanced soft limits. The recursion relations are illustrated through analytic calculation of tree-level scattering amplitudes in theories with a complex Schrödinger-type field, real scalar with linear dispersion relation, and real scalar with Lifshitz-type dispersion relation. Our results show that the landscape of gapless nonrelativistic EFTs with local S -matrix can be constrained by soft theorems and the consistency of the low-energy S -matrix similarly to massless relativistic EFTs. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
35. A recursion for a symmetric function generalization of the q-Dyson constant term identity.
- Author
-
Zhou, Yue
- Subjects
- *
GENERALIZATION , *LOGICAL prediction , *RECURSION theory - Abstract
In 2000, Kadell gave an orthogonality conjecture for a symmetric function generalization of the q -Dyson constant term identity or the Zeilberger–Bressoud q -Dyson theorem. The non-zero part of Kadell's orthogonality conjecture is a constant term identity indexed by a weak composition v = (v 1 , ... , v n) in the case when only one v i ≠ 0. This conjecture was first proved by Károlyi, Lascoux and Warnaar in 2015. They further formulated a closed-form expression for the above mentioned constant term in the case when all the parts of v are distinct. Recently we obtained a recursion for this constant term provided that the largest part of v occurs with multiplicity one in v. In this paper, we generalize our previous result to all weak compositions v. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
36. A dependently typed calculus with polymorphic subtyping.
- Author
-
Xue, Mingqi and Oliveira, Bruno C.d.S.
- Subjects
- *
CALCULUS , *RECURSION theory , *MODERN languages - Abstract
• A dependently-typed language that features implicit polymorphism, general recursion and explicit type-level computation. • Higher ranked subtype reasoning about the more-general-than relation between polymorphic types. • Fully mechanized proof of the type soundness and transitivity. A polymorphic subtyping relation, which relates more general types to more specific ones, is at the core of many modern functional languages. As those languages start moving towards dependently typed programming a natural question is how can polymorphic subtyping be adapted to such settings. This paper presents the dependent implicitly polymorphic calculus (λ I ∀): a simple dependently typed calculus with polymorphic subtyping. The subtyping relation in λ I ∀ generalizes the well-known polymorphic subtyping relation by Odersky and Läufer (1996). Because λ I ∀ is dependently typed, integrating subtyping in the calculus is non-trivial. To overcome many of the issues arising from integrating subtyping with dependent types, the calculus employs unified subtyping , which is a technique that unifies typing and subtyping into a single relation. Moreover, λ I ∀ employs explicit casts instead of a conversion rule, allowing unrestricted recursion to be naturally supported. We prove various non-trivial results, including type soundness and transitivity of unified subtyping. λ I ∀ and all corresponding proofs are mechanized in the Coq theorem prover. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
37. RSPCN: Super-Resolution of Digital Elevation Model Based on Recursive Sub-Pixel Convolutional Neural Networks.
- Author
-
Zhang, Ruichen, Bian, Shaofeng, and Li, Houpu
- Subjects
- *
CONVOLUTIONAL neural networks , *DIGITAL elevation models , *DEEP learning , *ALGORITHMS , *RECURSION theory , *PIXELS , *GEOMORPHOLOGY - Abstract
The digital elevation model (DEM) is known as one kind of the most significant fundamental geographical data models. The theory, method and application of DEM are hot research issues in geography, especially in geomorphology, hydrology, soil and other related fields. In this paper, we improve the efficient sub-pixel convolutional neural networks (ESPCN) and propose recursive sub-pixel convolutional neural networks (RSPCN) to generate higher-resolution DEMs (HRDEMs) from low-resolution DEMs (LRDEMs). Firstly, the structure of RSPCN is described in detail based on recursion theory. This paper explores the effects of different training datasets, with the self-adaptive learning rate Adam algorithm optimizing the model. Furthermore, the adding-"zero" boundary method is introduced into the RSPCN algorithm as a data preprocessing method, which improves the RSPCN method's accuracy and convergence. Extensive experiments are conducted to train the method till optimality. Finally, comparisons are made with other traditional interpolation methods, such as bicubic, nearest-neighbor and bilinear methods. The results show that our method has obvious improvements in both accuracy and robustness and further illustrate the feasibility of deep learning methods in the DEM data processing area. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.