The Experts below are selected from a list of 312 Experts worldwide ranked by ideXlab platform
Yoshiki Tsujii - One of the best experts on this subject based on the ideXlab platform.
-
Computability of a function with jumps
Topology and its Applications, 2005Co-Authors: Mariko Yasugi, Yoshiki TsujiiAbstract:AbstractGiven a strictly increasing computable sequence (called a base sequence) of real numbers (with respect to the Euclidean Topology), one can induce an effective uniformity for the real line, where the elements in the base sequence are regarded as isolated. The relation between two extended notions of computability of real sequences, one with respect to the Euclidean space with a limiting recursive modulus of convergence and one with respect to the induced uniform space, is discussed. As a consequence, we prove the equivalence of two extended notions of sequential computability (called L- and A- sequential computability) of a real function. This indicates that the two extended notions of sequential computability provide computational mechanisms of the same power. We will then characterize a piecewise continuous function to be computable (called para-computable here) as being L- (hence A-) sequentially computable and piecewise effectively continuous
-
Sequential Computability of a Function. Effective Fine Space and Limiting Recursion.
Journal of Universal Computer Science, 2005Co-Authors: Mariko Yasugi, Yoshiki Tsujii, Takakazu MoriAbstract:We consider real sequences in I =( 0, 1) and real functions on I.I t is first shown that, as for real sequences from I, R-computability (computability with respect to the Euclidean Topology) implies "weak Fine-computability." Using this re- sult, we show that "Fine-sequential computability" and "L ∗ -sequential computabil- ity" are equivalent for effectively locally Fine-continuous functions as well as for Fine- continuous functions.
-
Computability of a function with jumps: Effective uniformity and limiting recursion
Topology and its Applications, 2004Co-Authors: Mariko Yasugi, Yoshiki TsujiiAbstract:Abstract Given a strictly increasing computable sequence (called a base sequence) of real numbers (with respect to the Euclidean Topology), one can induce an effective uniformity for the real line, where the elements in the base sequence are regarded as isolated. The relation between two extended notions of computability of real sequences, one with respect to the Euclidean space with a limiting recursive modulus of convergence and one with respect to the induced uniform space, is discussed. As a consequence, we prove the equivalence of two extended notions of sequential computability (called L - and A - sequential computability) of a real function. This indicates that the two extended notions of sequential computability provide computational mechanisms of the same power. We will then characterize a piecewise continuous function to be computable (called para-computable here) as being L - (hence A -) sequentially computable and piecewise effectively continuous.
-
Two notions of sequential computability of a function with jumps
Electronic Notes in Theoretical Computer Science, 2002Co-Authors: Mariko Yasugi, Yoshiki TsujiiAbstract:Abstract Given a strictly increasing computable sequence of real numbers (with respect to the Euclidean Topology), one can define an effective uniform space of the real line, where the elements in the sequence are regarded as isolated. The relation between two notions of computability of real sequences, one with respect to the Euclidean space and one with respect to the uniform space as above, is discussed. As a consequence, we prove the equivalence of two notions of sequential computability of a function which is effectively uniformly continuous on the intervals between the given points and which may jump at those points.
Anik Trahan - One of the best experts on this subject based on the ideXlab platform.
-
Ideas from Zariski Topology in the Study of Cubical Homology
Canadian Journal of Mathematics, 2007Co-Authors: Tomasz Kaczynski, Marian Mrozek, Anik TrahanAbstract:Cubical sets and their homology have been used in dynamical systems as well as in digital imaging. We take a fresh look at this topic, following Zariski ideas from algebraic geometry. The cubical Topology is definedto be aTopology in R d in which aset is closed if andonlyif it is cubical. This concept is a convenient frame for describing a variety of important features of cubical sets. Separation axioms which, in general, are not satisfied here, characterize exactly those pairs of points which we want to distinguish. The noetherian property guarantees the correctness of the algorithms. Moreover, maps between cubical sets which are continuous and closed with respect to the cubical Topology are precisely those for whom the homology map can be defined and computed without grid subdivisions. A combinatorial version of the Vietoris-Begle theorem is derived. This theorem plays the central role in an algorithm computing homology of maps which are continuous with respect to the Euclidean Topology.
-
Ideas from Zariski Topology in the study of cubical sets, cubical maps, and their homology
2005Co-Authors: Tomasz Kaczynski, Marian Mrozek, Anik TrahanAbstract:Cubical sets and their homology have been used in dynamical systems as well as in digital imaging. We take a refreshing view on this topic, following Zariski ideas from algebraic geometry. The cubical Topology is defined to be a Topology in R d in which a set is closed if and only if it is cubical. This concept is a convenient frame for describing a variety of important features of cubical sets. Separation axioms which, in general, are not satisfied here, characterize exactly those pairs of points which we want to distinguish. The noetherian property guarantees the convergence of algorithms. Moreover, maps between cubical sets which are continuous and closed with respect to the cubical Topology are precisely those for whom the homology map can be defined and computed without grid subdivisions. A combinatorial version of the Vietoris-Begle is derived and used for an algorithm computing homology of maps which are continuous with respect to the Euclidean Topology.
Mariko Yasugi - One of the best experts on this subject based on the ideXlab platform.
-
Computability of a function with jumps
Topology and its Applications, 2005Co-Authors: Mariko Yasugi, Yoshiki TsujiiAbstract:AbstractGiven a strictly increasing computable sequence (called a base sequence) of real numbers (with respect to the Euclidean Topology), one can induce an effective uniformity for the real line, where the elements in the base sequence are regarded as isolated. The relation between two extended notions of computability of real sequences, one with respect to the Euclidean space with a limiting recursive modulus of convergence and one with respect to the induced uniform space, is discussed. As a consequence, we prove the equivalence of two extended notions of sequential computability (called L- and A- sequential computability) of a real function. This indicates that the two extended notions of sequential computability provide computational mechanisms of the same power. We will then characterize a piecewise continuous function to be computable (called para-computable here) as being L- (hence A-) sequentially computable and piecewise effectively continuous
-
Sequential Computability of a Function. Effective Fine Space and Limiting Recursion.
Journal of Universal Computer Science, 2005Co-Authors: Mariko Yasugi, Yoshiki Tsujii, Takakazu MoriAbstract:We consider real sequences in I =( 0, 1) and real functions on I.I t is first shown that, as for real sequences from I, R-computability (computability with respect to the Euclidean Topology) implies "weak Fine-computability." Using this re- sult, we show that "Fine-sequential computability" and "L ∗ -sequential computabil- ity" are equivalent for effectively locally Fine-continuous functions as well as for Fine- continuous functions.
-
Computability of a function with jumps: Effective uniformity and limiting recursion
Topology and its Applications, 2004Co-Authors: Mariko Yasugi, Yoshiki TsujiiAbstract:Abstract Given a strictly increasing computable sequence (called a base sequence) of real numbers (with respect to the Euclidean Topology), one can induce an effective uniformity for the real line, where the elements in the base sequence are regarded as isolated. The relation between two extended notions of computability of real sequences, one with respect to the Euclidean space with a limiting recursive modulus of convergence and one with respect to the induced uniform space, is discussed. As a consequence, we prove the equivalence of two extended notions of sequential computability (called L - and A - sequential computability) of a real function. This indicates that the two extended notions of sequential computability provide computational mechanisms of the same power. We will then characterize a piecewise continuous function to be computable (called para-computable here) as being L - (hence A -) sequentially computable and piecewise effectively continuous.
-
Two notions of sequential computability of a function with jumps
Electronic Notes in Theoretical Computer Science, 2002Co-Authors: Mariko Yasugi, Yoshiki TsujiiAbstract:Abstract Given a strictly increasing computable sequence of real numbers (with respect to the Euclidean Topology), one can define an effective uniform space of the real line, where the elements in the sequence are regarded as isolated. The relation between two notions of computability of real sequences, one with respect to the Euclidean space and one with respect to the uniform space as above, is discussed. As a consequence, we prove the equivalence of two notions of sequential computability of a function which is effectively uniformly continuous on the intervals between the given points and which may jump at those points.
Alex Simpson - One of the best experts on this subject based on the ideXlab platform.
-
LICS - A universal characterization of the closed Euclidean interval
Proceedings 16th Annual IEEE Symposium on Logic in Computer Science, 1Co-Authors: Martín Hötzel Escardó, Alex SimpsonAbstract:We propose a notion of interval object in a category with finite products, providing a universal property for closed and bounded real line segments. The universal property gives rise to an analogue of primitive recursion for defining computable functions on the interval. We use this to define basic arithmetic operations and to verify equations between them. We test the notion in categories of interest. In the category of sets, any closed and bounded interval of real numbers is an interval object. In the category of topological spaces, the interval objects are closed and bounded intervals with the Euclidean Topology. We also prove that an interval object exists in and elementary topos with natural numbers object.
Rudolf Fleischer - One of the best experts on this subject based on the ideXlab platform.
-
Decision trees: old and new results
Information and Computation, 1999Co-Authors: Rudolf FleischerAbstract:Abstract In this paper, we prove two general lower bounds for algebraic decision trees which test membership in a set S ⊆ R n which is defined by linear inequalities. Let rank( S ) be the maximal dimension of a linear sub- space contained in the closure of S (in Euclidean Topology). First we show that any decision tree for S which uses products of linear functions (we call such functions mlf- functions ) must have depth at least n −rank( S ). This solves an open question raised by A. C. Yao and can be used to show that mlf-functions are not really more powerful than simple comparisons between the input variables when computing the largest k out of n elements. Yao proved this result in the special case when products of at most two linear functions are allowed. Our proof also shows that any decision tree for this problem must have exponential size. Using the same methods, we can give an alternative proof of Rabin's theorem, namely that the depth of any decision tree for S using arbitrary analytic functions is at least n −rank( S ).