Search results for "Combinatorics"
showing 10 items of 1770 documents
Two shortest path metrics on well-formed parentheses strings
1996
We present an analysis of two transformations on well-formed parentheses strings. Using a lattice approach, the corresponding least-move distances are computable, the first in linear time and the second in quadratic time.
Hausdorff measures, Hölder continuous maps and self-similar fractals
1993
Let f: A → ℝn be Hölder continuous with exponent α, 0 < α ≼ 1, where A ⊂ ℝm has finite m-dimensional Lebesgue measure. Then, as is easy to see and well-known, the s-dimensional Hausdorif measure HS(fA) is finite for s = m/α. Many fractal-type sets fA also have positive Hs measure. This is so for example if m = 1 and f is a natural parametrization of the Koch snow flake curve in ℝ2. Then s = log 4/log 3 and α = log 3/log 4. In this paper we study the question of what s-dimensional sets in can intersect some image fA in a set of positive Hs measure where A ⊂ ℝm and f: A → ℝn is (m/s)-Hölder continuous. In Theorem 3·3 we give a general density result for such Holder surfacesfA which implies…
4-Manifold topology I: Subexponential groups
1995
The technical lemma underlying the 5-dimensional topological s-cobordism conjecture and the 4-dimensional topological surgery conjecture is a purely smooth category statement about locating ~-null immersions of disks. These conjectures are theorems precisely for those fundamental groups ("good groups") where the ~l-null disk lemma (NDL) holds. We expand the class of known good groups to all groups of subexponential growth and those that can be formed from these by a finite number of application of two opera- tions: (1) extension and (2) direct limit. The finitely generated groups in this class are amenable and no amenable group is known to lie outside this class.
On Banaschewski functions in lattices
1991
hold for all x, y ~ X. We call such a function z a Banaschewski function or a B-function on X. A lattice L is a B-lattice or antitonely complemented, if there is a B-function defined on the whole lattice L. For instance, Boolean lattices as well as orthocomplemented lattices are B-lattices. On the other hand, a B-lattice is not necessarily Boolean or orthocomplemented, although a distributive B-lattice is a Boolean lattice. It is shown later that a matroid (geometric) lattice is also a B-lattice. Naturally, our results include the lemma of Banaschewski [ 1, Lemma 4], by which the lattice of the subspaces of a vector space is a B-lattice. It should be emphasized that a B-function is supposed…
Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
2015
We study the structure of sets \(S\subseteq \{0, 1\}^n\) with small sensitivity. The well-known Simon’s lemma says that any \(S\subseteq \{0, 1\}^n\) of sensitivity \(s\) must be of size at least \(2^{n-s}\). This result has been useful for proving lower bounds on the sensitivity of Boolean functions, with applications to the theory of parallel computing and the “sensitivity vs. block sensitivity” conjecture.
Operators on PIP-Spaces and Indexed PIP-Spaces
2009
As already mentioned, the basic idea of pip-spaces is that vectors should not be considered individually, but only in terms of the subspaces V r (r Є F), the building blocks of the structure. Correspondingly, an operator on a pipspace should be defined in terms of assaying subspaces only, with the proviso that only continuous or bounded operators are allowed. Thus an operator is a coherent collection of continuous operators. We recall that in a nondegenerate pip-space, every assaying subspace V r carries its Mackey topology \(\tau (V_r , V \bar{r})\) and thus its dual is \(V \bar{r}\). This applies in particular to \(V^{\#}\) and V itself. For simplicity, a continuous linear map between two…
Foliations, Lineations and Lattice Preferred Orientation
1998
Many microstructures in rocks are defined by a preferred orientation of minerals or fabric elements. We distinguish foliations, lineations and lattice-preferred orientation.
Classifiers in Sinitic languages: From individuation to definiteness-marking
2012
Abstract This article examines the distribution and interpretation of the bare classifier phrase [Cl+N] in three Sinitic languages of Mandarin, Wu and Cantonese. We show that [Cl+N] can be interpreted as definite or indefinite depending on pragmatic factors related to information structure and word order. Syntactically, we claim that indefinite [Cl+N] has the maximal projection of ClP and that definite [Cl+N] is a DP, where the D head is filled by the classifier via Cl-to-D raising. Semantically, we claim that indefinite [Cl+N] is predicative, denoting sets of atomic entities and that definite [Cl+N] is derived from indefinite [Cl+N] by lifting it from predicates to Generalized Quantifiers.…
Polskie nazwy miejscowości z sufiksem -at-ka
2017
The article analyses Polish oikonyms ending in -atka, discussing whether this ending is a suffix, i.e. -at-ka, or simply appears to be one. Based on the method of morphological division, the findings suggest the existence of two distinctive groups of oikonyms: those with the suffix -at-ka, and those with three extended variants of this suffix: -ow-at-ka, -aw-at-ka and -ew-at-ka.
On Certain Metrizable Locally Convex Spaces
1986
Publisher Summary This chapter discusses on certain metrizable locally convex spaces. The linear spaces used are defined over the field IK of real or complex numbers. The word "space" will mean "Hausdorff locally convex space". This chapter presents a proposition which states if U be a neighborhood of the origin in a space E. If A is a barrel in E which is not a neighborhood of the origin and F is a closed subspace of finite codimension in E’ [σ(E’,E)], then U° ∩ F does not contain A° ∩ F. Suppose that U° ∩ F contain A° ∩ F. Then A° ∩ F is equicontinuous hence W is also equicontinuous. Since W° is contained in A, it follows that A is a neighborhood of the origin, a contradiction.