1,720,961 research outputs found
A journey through computability, topology and analysis
Full text linkThis thesis is devoted to the exploration of the complexity of some mathematical problems using the framework of computable analysis and descriptive set theory. We will especially focus on Weihrauch reducibility, as a means to compare the uniform computational strength of problems. After a short introduction of the relevant background notions, we investigate the uniform computational content of the open and clopen Ramsey theorems. In particular, since there is not a canonical way to phrase these theorems as multi-valued functions, we identify 8 different multi-valued functions (5 corresponding to the open Ramsey theorem and 3 corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch and arithmetic Weihrauch reducibility. We then discuss some new operators on multi-valued functions and study their algebraic properties and the relations with other previously studied operators on problems. These notions turn out to be extremely relevant when exploring the Weihrauch degree of the problem DS of computing descending sequences in ill-founded linear orders. They allow us to show that DS, and the Weihrauch equivalent problem BS of finding bad sequences through non-well quasi-orders, while being very "hard" to solve, are rather weak in terms of uniform computational strength. We then generalize DS and BS by considering Gamma-presented orders, where Gamma is a Borel pointclass or Delta11, Sigma11, Pi11. We study the obtained DS-hierarchy and BS-hierarchy of problems in comparison with the (effective) Baire hierarchy and show that they do not collapse at any finite level. Finally, we focus on the characterization, from the point of view of descriptive set theory, of some conditions involving the notions of Hausdorff/Fourier dimension and of Salem sets. We first work in the hyperspace K([0,1]) of compact subsets of [0,1] and show that the closed Salem sets form a Pi03-complete family. This is done by characterizing the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. We also show that the complexity does not change if we increase the dimension of the ambient space and work in K([0,1]^d). We also generalize the results by relaxing the compactness of the ambient space, and show that the closed Salem sets are still Pi03-complete when we endow K(R^d) with the Fell topology. A similar result holds also for the Vietoris topology. We conclude by showing how these results can be used to characterize the Weihrauch degree of the functions computing the Hausdorff and Fourier dimensions
Effective aspects of Hausdorff and Fourier dimension
Full text linkIn this paper, we study Hausdorff and Fourier dimension from the point of
view of effective descriptive set theory and Type-2 Theory of Effectivity.
Working in the hyperspace of compact subsets of , with
or , we characterize the complexity of the family
of sets having sufficiently large Hausdorff or Fourier dimension. This, in
turn, allows us to show that family of all the closed Salem sets is
-complete. One of our main tools is a careful analysis of the
effectiveness of a classical theorem of Kaufman. We furthermore compute the
Weihrauch degree of the functions computing Hausdorff and Fourier dimension of
closed sets.Comment: 36 page
On the descriptive complexity of Salem sets
Full text linkIn this paper we study the notion of Salem set from the point of view of
descriptive set theory. We first work in the hyperspace of
compact subsets of and show that the closed Salem sets form a
-complete family. This is done by characterizing the
complexity of the family of sets having sufficiently large Hausdorff or Fourier
dimension. We also show that the complexity does not change if we increase the
dimension of the ambient space and work in . We then
generalize the results by relaxing the compactness of the ambient space, and
show that the closed Salem sets are still -complete when
we endow the hyperspace of all closed subsets of with the Fell
topology. A similar result holds also for the Vietoris topology.Comment: Extended Lemma 3.1, fixed Lemma 5.3 and improved the presentation of
the results. To appear in Fundamenta Mathematica
Algebraic properties of the first-order part of a problem
Full text linkIn this paper we study the notion of first-order part of a computational
problem, first introduced by Dzhafarov, Solomon, and Yokoyama, which captures
the "strongest computational problem with codomain that is
Weihrauch reducible to ". This operator is very useful to prove separation
results, especially at the higher levels of the Weihrauch lattice. We explore
the first-order part in relation with several other operators already known in
the literature. We also introduce a new operator, called unbounded finite
parallelization, which plays an important role in characterizing the
first-order part of parallelizable problems. We show how the obtained results
can be used to explicitly characterize the first-order part of several known
problems.Comment: 41 pages. Updated after reviewer comment
The open and clopen Ramsey theorems in the Weihrauch lattice
Full text linkWe investigate the uniform computational content of the open and clopen
Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent
to from the point of view of reverse mathematics, there is not
a canonical way to phrase them as multivalued functions. We identify 8
different multivalued functions (5 corresponding to the open Ramsey theorem and
3 corresponding to the clopen Ramsey theorem) and study their degree from the
point of view of Weihrauch, strong Weihrauch and arithmetic Weihrauch
reducibility. In particular one of our functions turns out to be strictly
stronger than any previously studied multivalued functions arising from
statements around .Comment: Improved the presentation of lemmas 4.3 and 4.13. To appear in The
Journal of Symbolic Logi
Finding descending sequences through ill-founded linear orders
Full text linkIn this work we investigate the Weihrauch degree of the problem
of finding an infinite descending sequence through a given ill-founded linear
order, which is shared by the problem of finding a bad sequence
through a given non-well quasi-order. We show that , despite being
hard to solve (it has computable inputs with no hyperarithmetic solution), is
rather weak in terms of uniform computational strength. To make the latter
precise, we introduce the notion of the deterministic part of a Weihrauch
degree. We then generalize and by considering
-presented orders, where is a Borel
pointclass or , ,
. We study the obtained -hierarchy and
-hierarchy of problems in comparison with the (effective) Baire
hierarchy and show that they do not collapse at any finite level.Comment: Added errata. The problems and are not
Weihrauch-equivalent, and the separation has been proved in arXiv:2401.11807.
Please check the errata for the full list of change
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe 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
Full text link“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
Full text linkWe 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
- …
