ترغب بنشر مسار تعليمي؟ اضغط هنا

Continuous Regular Functions

108   0   0.0 ( 0 )
 نشر من قبل Philipp Hieronymi
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Following Chaudhuri, Sankaranarayanan, and Vardi, we say that a function $f:[0,1] to [0,1]$ is $r$-regular if there is a B{u}chi automaton that accepts precisely the set of base $r in mathbb{N}$ representations of elements of the graph of $f$. We show that a continuous $r$-regular function $f$ is locally affine away from a nowhere dense, Lebesgue null, subset of $[0,1]$. As a corollary we establish that every differentiable $r$-regular function is affine. It follows that checking whether an $r$-regular function is differentiable is in $operatorname{PSPACE}$. Our proofs rely crucially on connections between automata theory and metric geometry developed by Charlier, Leroy, and Rigo.



قيم البحث

اقرأ أيضاً

We construct, under the assumption that union of less than continuum many meager subsets of R is meager in R, an additive connectivity function f:R-->R with Cantor intermediate value property which is not almost continuous. This gives a partial answe r to a question of D. Banaszewski. We also show that every extendable function g:R-->R with a dense graph satisfies the following stronger version of the SCIVP property: for every a<b and every perfect set K between g(a) and g(b) there is a perfect subset C of (a,b) such that g[C] subset K and g|C is continuous strictly increasing. This property is used to construct a ZFC example of an additive almost continuous function f:R-->R which has the strong Cantor intermediate value property but is not extendable. This answers a question of H. Rosen. This also generalizes Rosens result that a similar (but not additive) function exists under the assumption of the continuum hypothesis.
A notable feature of the TTE approach to computability is the representation of the argument values and the corresponding function values by means of infinitistic names. Two ways to eliminate the using of such names in certain cases are indicated in the paper. The first one is intended for the case of topological spaces with selected indexed denumerable bases. Suppose a partial function is given from one such space into another one whose selected base has a recursively enumerable index set, and suppose that the intersection of base open sets in the first space is computable in the sense of Weihrauch-Grubba. Then the ordinary TTE computability of the function is characterized by the existence of an appropriate recursively enumerable relation between indices of base sets containing the argument value and indices of base sets containing the corresponding function value.This result can be regarded as an improvement of a result of Korovina and Kudinov. The second way is applicable to metric spaces with selected indexed denumerable dense subsets. If a partial function is given from one such space into another one, then, under a semi-computability assumption concerning these spaces, the ordinary TTE computability of the function is characterized by the existence of an appropriate recursively enumerable set of quadruples. Any of them consists of an index of element from the selected dense subset in the first space, a natural number encoding a rational bound for the distance between this element and the argument value, an index of element from the selected dense subset in the second space and a natural number encoding a rational bound for the distance between this element and the function value. One of the examples in the paper indicates that the computability of real functions can be characterized in a simple way by using the first way of elimination of the infinitistic names.
100 - Taras Banakh 2019
A function $f:Xto Y$ between topological spaces is called $sigma$-$continuous$ (resp. $barsigma$-$continuous$) if there exists a (closed) cover ${X_n}_{ninomega}$ of $X$ such that for every $ninomega$ the restriction $f{restriction}X_n$ is continuous . By $mathfrak c_sigma$ (resp. $mathfrak c_{barsigma}$) we denote the largest cardinal $kappalemathfrak c$ such that every function $f:Xtomathbb R$ defined on a subset $Xsubsetmathbb R$ of cardinality $|X|<kappa$ is $sigma$-continuous (resp. $barsigma$-continuous). It is clear that $omega_1lemathfrak c_{barsigma}lemathfrak c_sigmalemathfrak c$. We prove that $mathfrak plemathfrak q_0=mathfrak c_{barsigma}=min{mathfrak c_sigma,mathfrak b,mathfrak q}lemathfrak c_sigmalemin{mathrm{non}(mathcal M),mathrm{non}(mathcal N)}$. The equality $mathfrak c_{barsigma}=mathfrak q_0$ resolves a problem from the initial version of the paper.
60 - Francesco Dagnino 2020
Inference systems are a widespread framework used to define possibly recursive predicates by means of inference rules. They allow both inductive and coinductive interpretations that are fairly well-studied. In this paper, we consider a middle way int erpretation, called regular, which combines advantages of both approaches: it allows non-well-founded reasoning while being finite. We show that the natural proof-theoretic definition of the regular interpretation, based on regular trees, coincides with a rational fixed point. Then, we provide an equivalent inductive characterization, which leads to an algorithm which looks for a regular derivation of a judgment. Relying on these results, we define proof techniques for regular reasoning: the regular coinduction principle, to prove completeness, and an inductive technique to prove soundness, based on the inductive characterization of the regular interpretation. Finally, we show the regular approach can be smoothly extended to inference systems with corules, a recently introduced, generalised framework, which allows one to refine the coinductive interpretation, proving that also this flexible regular interpretation admits an equivalent inductive characterisation.
Assume that X is a metrizable separable space, and each clopen-valued lower semicontinuous multivalued map Phi from X to Q has a continuous selection. Our main result is that in this case, X is a sigma-space. We also derive a partial converse implica tion, and present a reformulation of the Scheepers Conjecture in the language of continuous selections.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا