The complexity of isomorphism for complete theories of linear orders with unary predicates

Suppose A is a linear order, possibly with countably many unary predicates added. We classify the isomorphism relation for countable models of \(\text {Th}(A)\) up to Borel bi-reducibility, showing there are exactly five possibilities and characterizing exactly when each can occur in simple model-theoretic terms. We show that if the language is finite (in particular, if there are no unary predicates), then the theory is \(\aleph _0\)-categorical or Borel complete; this generalizes a theorem due to Schirmann (Theories des ordres totaux et relations dequivalence. Master’s thesis, Universite de Paris VII, 1997).     

Random partitioning over a sparse contingency table

The present article investigates a class of random partitioning distributions of a positive integer. This class is called the limiting conditional compound poisson (LCCP) distribution and characterized by the law of small numbers. Accordingly the LCCP distribution explains the limiting behavior of counts on a sparse contingency table by the frequencies of frequencies. The LCCP distribution is constructed via some combinations of conditioning and limiting, and this view reveals that the LCCP distribution is a subclass of several known classes that depend on a Bell polynomial. It follows that the limiting behavior of a Bell polynomial provides new asymptotics for a sparse contingency table. Also the Neyman Type A distribution and the Thomas distribution are revisited as the basis of the sparsity.     

Random walks in a strongly sparse random environment

The integer points (sites) of the real line are marked by the positions of a standard random walk with positive integer jumps. We say that the set of marked sites is weakly, moderately or strongly sparse depending on whether the jumps of the random walk are supported by a bounded set, have finite or infinite mean, respectively. Focussing on the case of strong sparsity and assuming additionally that the distribution tail of the jumps is regularly varying at infinity we consider a nearest neighbor random walk on the set of integers having jumps $\pm 1$ with probability $1∕2$ at every nonmarked site, whereas a random drift is imposed at every marked site. We prove new distributional limit theorems for the so defined random walk in a strongly sparse random environment, thereby complementing results obtained recently in Buraczewski et al. (2019) for the case of moderate sparsity and in Matzavinos et al. (2016) for the case of weak sparsity. While the random walk in a strongly sparse random environment exhibits either the diffusive scaling inherent to a simple symmetric random walk or a wide range of subdiffusive scalings, the corresponding limit distributions are non-stable.     

Group-universal unary varieties

LetV be a variety of unary algebras and letM(V) be the monoid of all unary polynomials ofV. Then every group appears as the automorphism group of an algebraA∈V if and only if the left ideals ofM(V) do not form an inclusion-ordered chain. The support of the National Research Council of Canada is gratefully acknowledged. Presented by J. Mycielski.     

Partition theorems for unary algebras

Those unary algebras (A, ?) (A a set, ? a mapping from A into A) are characterized for which an analog of Ramsey's theorem holds.     

Optimization with unary functions

Most nonlinear programming problems consist of functions which are sums of unary functions of linear functions. Advantage can be taken of this form to calculate second and higher order derivatives easily and at little cost. Using these, high order optimization techniques such as Halley's method can be utilized to accelerate the rate of convergence to the solution. These higher order derivatives can also be used to compute second order sensitivity information. These techniques are applied to the solution of the classical chemical equilibrium problem.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research and by the Office of Naval Research grant N00014-86-K0052.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research.     

Bounded iteration and unary functions

The set of unary functions of complexity classes defined by using bounded primitive recursion is inductively characterized by means of bounded iteration. Elementary unary functions, linear space computable unary functions and polynomial space computable unary functions are then inductively characterized using only composition and bounded iteration. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Characterization of unary developmental languages

Developmental systems and languages have in recent years been the subject matter of active investigation, both because they are useful in discussing biological development and because they provide some fresh insights into formal language theory. In this paper, we investigate unary developmental systems and languages, which are distinguished by the property that the alphabet involved in their definition has only one symbol in it.     

Twenty five (unary version)

In the article, we show by means of a tune, dedicated to the memory of K. Beidar, how one can (without using highly specialized musical editors) store and transmit arbitrary music information in a degree of completeness that is sufficient for successful employment by experts, professionals, fanciers, amateurs, and dilettantes. The text below is set up in by the author’s original C program, which treats a two-dimensional, three-columned integer array as some essential information about a piece of music up to the exact observation of phrasing. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 12, No. 3, pp. 225–238, 2006.     

Quasiidentities of finite unary algebras

Translated from Algebra i Logika, Vol. 28, No. 5, pp. 493–512, September–October, 1989.     

Primitive iteration and unary functions

Programming practice suggests a general notion of primitive iteration which subsumes the for-until-do construct as well as all known primative iteration operators. This leads to new iterative characterizations of primitive computable functions usable in computer science.     

Semivarieties and Schreier varieties of unary algebras

A correction is provided for one result of a paper by Shafaat [1], and it is proven that the set of Schreier varieties of algebras 〈A;⁺1〉 with two unary operations has the cardinality of the continuum.     

Diophantine representation of enumerable predicates

This paper is the author's abstract of dissertation in partial fulfillment of the requirements for the degree of Doctor of Physicomathematical Sciences. The dissertation was defended on February 24, 1972 at a session of the faculty council of the V. A. Steklov Mathematics Institute, Academy of Sciences of the SSSR. The official opponents were: Doctor of Physicomathematical Sciences S. I. Adyan; Corresponding Member of the Academy of Sciences of the USSR Yu. L. Ershov; and Corresponding Member of the Academy of Sciences of the USSR D. K. Faddeev.Translated from Matematicheskie Zametki, Vol. 12, No. 1, pp. 115–120, July, 1972.