Search results for " function"
showing 10 items of 9395 documents
A Survey of Continuous-Time Computation Theory
1997
Motivated partly by the resurgence of neural computation research, and partly by advances in device technology, there has been a recent increase of interest in analog, continuous-time computation. However, while special-case algorithms and devices are being developed, relatively little work exists on the general theory of continuous- time models of computation. In this paper, we survey the existing models and results in this area, and point to some of the open research questions. Final Draft peerReviewed
Finite State Transducers with Intuition
2010
Finite automata that take advice have been studied from the point of view of what is the amount of advice needed to recognize nonregular languages. It turns out that there can be at least two different types of advice. In this paper we concentrate on cases when the given advice contains zero information about the input word and the language to be recognized. Nonetheless some nonregular languages can be recognized in this way. The help-word is merely a sufficiently long word with nearly maximum Kolmogorov complexity. Moreover, any sufficiently long word with nearly maximum Kolmogorov complexity can serve as a help-word. Finite automata with such help can recognize languages not recognizable …
Size of Quantum Finite State Transducers
2007
Sizes of quantum and deterministic finite state transducers are compared in the case when both quantum and deterministic finite state transducers exist. The difference in size may be exponential.
On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards
2007
The guarded fragment of first-order logic, GF, enjoys the finite model property, so the satisfiability and the finite satisfiability problems coincide. We are concerned with two extensions of the two-variable guarded fragment that do not possess the finite model property, namely, GF2 with equivalence and GF2 with transitive guards. We prove that in both cases every finitely satisfiable formula has a model of at most double exponential size w.r.t. its length. To obtain the result we invent a strategy of building finite models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2NEXPTIME-upper bound on the complexity of the fini…
Orlicz–Sobolev extensions and measure density condition
2010
Abstract We study the extension properties of Orlicz–Sobolev functions both in Euclidean spaces and in metric measure spaces equipped with a doubling measure. We show that a set E ⊂ R satisfying a measure density condition admits a bounded linear extension operator from the trace space W 1 , Ψ ( R n ) | E to W 1 , Ψ ( R n ) . Then we show that a domain, in which the Sobolev embedding theorem or a Poincare-type inequality holds, satisfies the measure density condition. It follows that the existence of a bounded, possibly non-linear extension operator or even the surjectivity of the trace operator implies the measure density condition and hence the existence of a bounded linear extension oper…
Probabilistic Interpretations of Predicates
2016
In classical logic, any m-ary predicate is interpreted as an m-argument two-valued relation defined on a non-empty universe. In probability theory, m-ary predicates are interpreted as probability measures on the mth power of a probability space. m-ary probabilistic predicates are equivalently semantically characterized as m-dimensional cumulative distribution functions defined on \(\mathbb {R}^m\). The paper is mainly concerned with probabilistic interpretations of unary predicates in the algebra of cumulative distribution functions defined on \(\mathbb {R}\). This algebra, enriched with two constants, forms a bounded De Morgan algebra. Two logical systems based on the algebra of cumulative…
Proper 1-ball contractive retractions in Banach spaces of measurable functions
2005
In this paper we consider the Wosko problem of evaluating, in an infinite-dimensional Banach space X, the infimum of all k > 1 for which there exists a k-ball contractive retraction of the unit ball onto its boundary. We prove that in some classical Banach spaces the best possible value 1 is attained. Moreover we give estimates of the lower H-measure of noncompactness of the retractions we construct. 1. Introduction Let X be an infinite-dimensional Banach space with unit closed ball B(X) and unit sphere S(X). It is well known that, in this setting, there is a retraction of B(X) onto S(X), that is, a continuous mapping R : B(X) ! S(X) with Rx = x for all x 2 S(X). In (4) Benyamini and Sternf…
Interpolating sequences on uniform algebras
2009
Abstract We consider the problem of whether a given interpolating sequence for a uniform algebra yields linear interpolation. A positive answer is obtained when we deal with dual uniform algebras. Further we prove that if the Carleson generalized condition is sufficient for a sequence to be interpolating on the algebra of bounded analytic functions on the unit ball of c 0 , then it is sufficient for any dual uniform algebra.
An optimal extension of Marstrand?s plane-packing theorem
2003
We prove that if F is a subset of the 2-dimensional unit sphere in $\mathbb{R}^3$, with Hausdorff dimension strictly greater than 1, and E is a subset of $\mathbb{R}^3$ such that for each $e \in F$, E contains a plane perpendicular to the vector e, then E must have positive 3-dimensional Lebesgue measure.
Almost disjoint families of countable sets and separable complementation properties
2012
We study the separable complementation property (SCP) and its natural variations in Banach spaces of continuous functions over compacta $K_{\mathcal A}$ induced by almost disjoint families ${\mathcal A}$ of countable subsets of uncountable sets. For these spaces, we prove among others that $C(K_{\mathcal A})$ has the controlled variant of the separable complementation property if and only if $C(K_{\mathcal A})$ is Lindel\"of in the weak topology if and only if $K_{\mathcal A}$ is monolithic. We give an example of ${\mathcal A}$ for which $C(K_{\mathcal A})$ has the SCP, while $K_{\mathcal A}$ is not monolithic and an example of a space $C(K_{\mathcal A})$ with controlled and continuous SCP …