Complete problems withL-samplable distributions

The average case complexity classes P, L-samplable and NL, L-samplable are defined. We show that Deterministic Bounded Halting is complete for P, L-samplable and that Graph Reachability is complete for NL-samplable, both problems with a universal logspace samplable distribution.     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

Construction of Certain Cyclic Distance-Preserving Codes Having Linear-Algebraic Characteristics

An ordered list of binary words of length n is called a distance-preserving m, n-code, if the list distance between two words is equal to their Hamming distance, for distances up to m. A technique for constructing cyclic m, n-codes is presented, based on the standard Gray code and on some simple tools from linear algebra.     

Groups with a class of Frobenius-Abelian elements

Let G be a group, a G ^#, and let F_a be the set of all Frobenius subgroups with noninvariant factor a in G. In Theorems 1–3, we show that if a ² 1and G has sufficiently many subgroups a, a ^g F _a. then a^G F _a.An element a is called (almost) Frobenius if, for (almost) all elements a ^g,the subgroup a, a ^g either belongs to F _a or is Abelian. In Theorems 4–5, we investigate the structure of a ^G in G for the case where a is an (almost) Frobenius-Abelian element of order 2.In Theorem 6, we prove that a binary factorable group is locally completely factorable. Translated fromAlgebra i Logika, Vol. 34, No. 5, pp. 531–549, September-October, 1995.     

Die Verbände mit nichteinfacher Funktionenalgebra

Let V; , be a lattice, thenF(V), the set of all functions fromV toV, becomes a lattice by defining the operations and pointwise. If we also consider the composition of functions as an operation onF(V), we get the function algebra F(V); , ,·. In this paper we give a characterization of the lattices with nonsimple function algebras. Moreover, the congruence lattice of these function algebras turns out to be a three-element chain.     

Laplace Operators on Fractal Lattices with Random Blow-Ups

Starting from a finitely ramified self-similar set X we can construct an unbounded set X by blowing-up the initial set X. We consider random blow-ups and prove elementary properties of the spectrum of the natural Laplace operator on X (and on the associated lattice). We prove that the spectral type of the operator is almost surely deterministic with the blow-up and that the spectrum coincides with the support of the density of states almost surely (actually, our result is more precise). We also prove that if the density of states is completely created by the so-called Neuman–Dirichlet eigenvalues, then almost surely the spectrum is pure point with compactly supported eigenfunctions.     

A Homotopy 2-Groupoid of a Hausdorff Space

If X is a Hausdorff space we construct a 2-groupoid G ₂ X with the following properties. The underlying category of G ₂ X is the `path groupoid" of X whose objects are the points of X and whose morphisms are equivalence classes f, g of paths f, g in X under a relation of thin relative homotopy. The groupoid of 2-morphisms of G ₂ X is a quotient groupoid X / N X, where X is the groupoid whose objects are paths and whose morphisms are relative homotopy classes of homotopies between paths. N X is a normal subgroupoid of X determined by the thin relative homotopies. There is an isomorphism G ₂ X(f,f) ₂(X, f(0)) between the 2-endomorphism group of f and the second homotopy group of X based at the initial point of the path f. The 2-groupoids of function spaces yield a 2-groupoid enrichment of a (convenient) category of pointed spaces.We show how the 2-morphisms may be regarded as 2-tracks. We make precise how cubical diagrams inhabited by 2-tracks can be pasted.     

Subgroups of free groups

With each subgroup A of a free group F there is associated a number FA called the quasi-index. It is proved that FA=ªA¦ if ¦FA¦ is finite. Some properties of the quasi-index are also established, in particular that the analog of Lagrange's theorem is valid for it: FB FA AB if A B as well as generalizations of Howson's and Byrnes' theorems.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, Nos. 7 and 8, pp. 1115–1119, July–August, 1991.     

Convergence of epigraphs and of sublevel sets

Let LSC(X) be the set of the proper lower semicontinuous extended real-valued functions defined on a metric spaceX. Given a sequence f _n in LSC(X) and a functionf LSC(X), we show that convergence of f _n tof in several variational convergence modes implies that for each , the sublevel set at height off is the limit, in the same variational sense, of an appropriately chosen sequence of sublevel sets of thef _n, at height _n approaching . The converse holds true whenever a form of stability of the sublevel sets of the limit function is verified. The results are obtained by regarding a hyperspace topology as the weakest topology for which each member of an appropriate family of excess functionals is upper semicontinuous, and each member of an appropriate family of gap functionals is lower semicontinuous. General facts about the representation of hyperspace topologies in this manner are given.     

Vacuum polarization of a complex automorphic scalar field in two-dimensional spacetime with closed null geodesics and the time-machine problem

A quantized automorphic scalar field in two-dimensional spacetime with closed null geodesics (Cauchy horizon) is considered. The renormalized energy—momentum tensor T _v^ren is obtained. It is shown that for specific values of the automorphic parameter T _v^ren remains regular on the Cauchy horizon.Kazan Pedagogical Institute. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 102, No. 1 pp. 134–149, January, 1995.     

Flag-Transitive 2-Designs Arising from Line-Spreads in PG(2n-1,2)

A Singer cycle in GL(n,q) is an element of order q permuting cyclically all the nonzero vectors. Let be a Singer cycle in GL(2n,2). In this note we shall count the number of lines in PG (2n-1,2) whose orbit under the subgroup of index 3 in the Singer group is a spread. The lines constituting such a spread are permuted cyclically by the group ³, hence gives rise to a flag-transitive 2-(2²ⁿ ,4,1) design.     

A simplicial 4-arrangement of 33 hyperplanes

We show in this paper that the projective d-arrangement ^d formed by the facet hyperplanes of a cross-polytope, its hyperplanes of mirror symmetry, and the hyperplane at infinity is simplicial precisely for d4.The arrangement ⁴ is the only simplicial 4-arrangement presently known that does not lie in a natural sequence of analogous arrangements that are simplicial in each dimension. It has flat vector g=409, 746, 290, 33 and face vector f=409, 4104, 12336, 14400, 5760.     

Wijsman convergence: A survey

A net A of nonempty closed sets in a metric space X, d is declaredWijsman convergent to a nonempty closed setA provided for eachx X, we haved(x, A)=lim d(x, A). Interest in this convergence notion originates from the seminal work of R. Wijsman, who showed in finite dimensions that the conjugate map for proper lower semicontinuous convex functions preserves convergence in this sense, where functions are identified with their epigraphs. In this paper, we review the attempts over the last 25 years to produce infinite-dimensional extensions of Wijsman's theorem, and we look closely at the topology of Wijsman convergence in an arbitrary metric space as well. Special emphasis is given to the developments of the past five years, and several new limiting counterexamples are presented.     

Optimal boundary regularity for minimal surfaces with a free boundary

Let x(w), w=u+iv B, be a minimal surface in ³ which is bounded by a configuration , S consisting of an arc and of a surface S with boundary. Suppose also that x(w) is area minimizing with respect to , S. Under appropriate regularity assumptions on and S, we can prove that the first derivatives of x(u, v) are Hölder continuous with the exponent =1/2 up to the free part of B which is mapped by x(w) into S. An example shows that this regularity result is optimal.     

RC *-fields

It is stated that if a Boolean family W of valuation rings of a field F satisfies the block approximation property (BAP) and a global analog of the Hensel-Rychlick property (THR), in which case F, W is called an RC^*-field, then F is regularly closed with respect to the family W (The-orem 1). It is proved that every pair F, W, where W is a weakly Boolean family of valuation rings of a field F, is embedded in the RC^*-field F₀, W₀ in such a manner that R₀ R₀ F, R₀ W₀ is a continuous map, W₀ is homeomorphic over W to a given Boolean space, and R₀ is a superstructure of R₀ F for every R₀ W₀ (Theorem 2).Translated fromAlgebra i Logika, Vol. 33, No. 4, pp. 367–386, July-August, 1994.     

Probabilistic characterizations of the Generalized Domain of Attraction of the multivariate normal law

For independent identically distributed random vectors,X _i , we give necessary and sufficient probabilistic conditions for their common distribution to belong to the Generalized Domain of Attraction of the multivariate normal law. The first condition says that after projecting onto any direction, , the sum of squares, _i ¹⁼¹ X _i , ², properly normalized, converges to one in probability uniformly over the unit sphere. The second condition says that max X _i , ²/ _n ⁱ⁼¹ X _i , ² converges to zero in probability uniformly over the unit sphere.     

Decision-procedures for invariant properties of short algorithms

For a class of algorithms R satisfying sufficiently general conditions and an enumeration of the algorithms of this class, it is proved that if the algorithm from R with code m in this enumeration algorithmically decides a property, nontrivial to N₁ and invariant (with respect to extensional equality) up to N, then for N max (t²(c)t⁵(N₁, t²(a)) one has m t^–3(N), where the constantsa, c and the function t are indicated in the text of the paper, t^–3(N) is used instead of t^–1(t^–1(t^–1(N))), and finally, t^–1(x)=yx[t(y)x]. For natural enumerations the constantsa, c are not large, and the function t does not grow too rapidly. From the result obtained also follows a generalization of a theorem of Rice in a form close to that proved in [2].Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 73–76, 1979.In conclusion, the author thanks the participants in the Leningrad seminar on mathematical logic for valuable comments.     

Strong normalization of barrecursive terms without using infinite terms

In this paper a new proof of the strong normalization theorem (SN) for barrecursive terms is presented.The proof is based on a syntactical version of Howard's compactness of functionals of finite type (see [T, 2.8.6]). The proofs of Tait [Ta], Luckhardt [L], and Vogel [V] are all based on continuity. These proofs use infinite terms: ifT ₀,T ₁, ... is an infinite sequence of terms of type , then T ₀,T ₁, ... is an infinite term of type (0). The proof below does not make use of infinite terms.     

Maslov Index and a Central Extension of the Symplectic Group

In this paper we show that over any field K of characteristic different from 2, the Maslov index gives rise to a 2-cocycle on the stable symplectic group with values in the Witt group. We also show that this cocycle admits a natural reduction to I ²(K) and that the induced natural homomorphism from K ₂ Sp(K)I ²(K) is indeed the homomorphism given by the symplectic symbol {x, y} mapping to the Pfister form 1, -x 1, –y.     

Operating on the universe

Summary In spite of the fact that the Z.F. universe is not well-ordered, it behaves in some respects like the ordinals. It is possible to define on it the usual operations of addition, multiplication and exponentiation, which enjoy similar properties to those on the ordinals. Further when restricted to the ordinals, the operations coincide, so that ordinal arithmetic can be regarded as a restriction of the universe arithmetic. But more than that, rank which retracts the universe of sets onto the ordinals is a homomorphism between the universe arithmetical structure V,+,·,exp and the ordinal arithmetical structure Ord, +, ·,exp.