1,721,060 research outputs found
Foundations of Online Structure Theory II: The Operator Approach
Get PDFWe introduce a framework for online structure theory. Our approach
generalises notions arising independently in several areas of computability
theory and complexity theory. We suggest a unifying approach using operators
where we allow the input to be a countable object of an arbitrary complexity.
We give a new framework which (i) ties online algorithms with computable
analysis, (ii) shows how to use modifications of notions from computable
analysis, such as Weihrauch reducibility, to analyse finite but uniform
combinatorics, (iii) show how to finitize reverse mathematics to suggest a fine
structure of finite analogs of infinite combinatorial problems, and (iv) see
how similar ideas can be amalgamated from areas such as EX-learning, computable
analysis, distributed computing and the like. One of the key ideas is that
online algorithms can be viewed as a sub-area of computable analysis.
Conversely, we also get an enrichment of computable analysis from classical
online algorithms
Undecidability Results for low complexity degree structures (Extended Abstract)
No full textRod Downey , Victoria University of Wellington New Zealand Andr'e Nies y The University of Chicago Chicago Illinois 60637 USA Abstract We prove that the theory of EXPTIME degrees with respect to polynomial time Turing and many-one reducibility is undecidable. To do so we use a coding method based on ideal lattices of Boolean algebras which was introduced in [7]. The method can be applied in fact to all hyper-polynomial time classes. 1 Introduction If h is a time constructible function which dominates all polynomials, then, by the methods of the deterministic time hierarchy theorem, DT IME(h) properly contains P. Therefore, a polynomial time reducibility like polynomial time many--one or Turing reducibility induces a nontrivial degree structure on DT IME(h). This degree structure is an uppersemilattice with least element 0. Moreover, by the methods of Ladner ([6], also see [4], Chapter I.7), this degree structure is dense. This was so far the only fact known to hold in general for..
Five Lectures on Algorithmic Randomness
No full textThis paper follows on from the author’s Five Lectures on Algorithmic Randomness. It is concerned with material not found in that long paper, concentrating on Martin-Löf lowness and triviality. We present a hopefully user-friendly account of the decanter method, and discuss recent results of the author with Peter Cholak and Noam Greenberg concerning the class of strongly jump traceable reals introduced b
On Presentations of Algebraic Structures
No full textThis paper is an expanded version of an part of a series of invited lectures given by the author during May 1995 in Siena, Italy to the COLORET II conference. This work is partially supported by Victoria University IGC and the Marsden Fund for Basic Science under grant VIC-509. This paper is dedicated to the memory of my friend and teacher Chris Ash who contributed so much to effective structure theory and who left us far too young early in 199
Computability, Definability and Algebraic Structures
No full textThis paper is an expanded version of an invited lecture \Every Set has a Least Jump Enumeration" given by the author during June, 1999 in Hsi-Tou, Taiwan, as part of the 7th Asian Logic Conference. This work is partially supported by the New Zealand Marsden Fund for Basic Science. I wish to thank the organizers of this conference for their hospitality and beautiful organization. Additional thanks to Reed Solomon, Richard Coles, and Denis Hirschfeldt who supplied comment and correction
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Kolmogorov Complexity and Solovay Functions
Get PDFSolovay (1975) proved that there exists a computable upper bound~ of the prefix-free Kolmogorov complexity function~ such that for infinitely many~. In this paper, we consider the class of computable functions~ such that for all~ and for infinitely many~, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality
- …
