Categorical abstract algebraic logic categorical algebraization of first-order logic without terms

An algebraization of multi-signature first-order logic without terms is presented. Rather than following the traditional method of choosing a type of algebras and constructing an appropriate variety, as is done in the case of cylindric and polyadic algebras, a new categorical algebraization method is used: The substitutions of formulas of one signature for relation symbols in another are treated in the object language. This enables the automatic generation via an adjunction of an algebraic theory. The algebras of this theory are then used to algebraize first-order logic.Partially supported by National Science Foundation grant CCR - 9593168     

A preliminary test procedure for the scale parameter of exponential distribution when the selection parameter is unknown

Summary A preliminary test estimator is considered for the scale parameter of the two-parameter exponential distribution with unknown selection parameter, where the distribution does not satisfy the regularity condition of Wilks' theorem—the density is not differentiable. A method of specifying the level of significance of the preliminary test based on is proposed AIC. This work was partly supported by Scientific Research Fund No. 58450058 from the Ministry of Education of Japan. The Institute of Statistical Mathematics     

Dimensions, matroids, and dense pairs of first-order structures

A structure M is pregeometric if the algebraic closure is a pregeometry in all structures elementarily equivalent to M. We define a generalisation: structures with an existential matroid. The main examples are superstable groups of Lascar U-rank a power of ω and d-minimal expansion of fields. Ultraproducts of pregeometric structures expanding an integral domain, while not pregeometric in general, do have a unique existential matroid.Generalising previous results by van den Dries, we define dense elementary pairs of structures expanding an integral domain and with an existential matroid, and we show that the corresponding theories have natural completions, whose models also have a unique existential matroid. We also extend the above result to dense tuples of structures.     

Inference of Probabilities over a Stochastic IL-System by Quantifier Elimination

An algebraic approach based on quantifier elimination is proposed for the inference of probabilistic parameters over stochastic Lindenmayer systems with interaction, IL-systems. We are concerned with a multi-cellular organism as an instance of a stochastic IL system. The organism starts with one or a few cells, and develops different types of cells with distinct functions. We have constructed a simple model with cell-type order conservation and have assessed conditions for high cell-type diversity. This model is based on the stochastic IL-system for three types of cells. The cell-type order conservation corresponds to interaction terms in the IL-system. In our model, we have successfully inferred algebraic relations between the probabilities for cell-type diversity by using a symbolic method, quantifier elimination (QE). Surprisingly, three modes for the proliferation and transition rates emerged for various ratios of the initial cells to the developed cells. Furthermore, we have found that the high cell-type diversity pattern originates from the cell-type order conservation. Thus, QE has yielded analysis of the IL-system, which has revealed that, during the developing process of multi-cellular organisms, complex but explicit relations exist between cell-type diversity patterns and developmental rates.      

Real-time dispatch of trams in storage yards

Real-time dispatch problems arise when preparing and executing the daily schedule of local transport companies. We consider the daily dispatch of transport vehicles like trams in storage yards. Immediately on arrival, each tram has to be assigned to a location in the depot and to an appropriate round trip of the next schedule period. In order to achieve a departure order satisfying the scheduled demand, shunting of vehicles may be unavoidable. Since shunting takes time and causes operational cost, the number of shunting movements should be minimized without violation of operational constraints. As an alternative, we may serve some round trips with trams of type differing from the requested type. In practice, the actual arrival order of trams may differ substantially from the scheduled arrival order. Then, dispatch decisions are due within a short time interval and have to be based on incomplete information. For such real-time dispatch problems, we develop combinatorial optimization models and exact as well as heuristic algorithms. Computational experience for real-world and random data shows that the derived methods yield good (often optimal) solutions within the required tight time bounds. This revised version was published online in June 2006 with corrections to the Cover Date.     

The increment ratio statistic

We introduce a new statistic written as a sum of certain ratios of second-order increments of partial sums process of observations, which we call the increment ratio (IR) statistic. The IR statistic can be used for testing nonparametric hypotheses for d-integrated () behavior of time series X_t, including short memory (d=0), (stationary) long-memory and unit roots (d=1). If S_n behaves asymptotically as an (integrated) fractional Brownian motion with parameter , the IR statistic converges to a monotone function Λ(d) of as both the sample size N and the window parameter m increase so that N/m→∞. For Gaussian observations X_t, we obtain a rate of decay of the bias EIR-Λ(d) and a central limit theorem (N/m)^1/2(IR-EIR)→N(0,σ²(d)), in the region . Graphs of the functions Λ(d) and σ(d) are included. A simulation study shows that the IR test for short memory (d=0) against stationary long-memory alternatives has good size and power properties and is robust against changes in mean, slowly varying trends and nonstationarities. We apply this statistic to sequences of squares of returns on financial assets and obtain a nuanced picture of the presence of long-memory in asset price volatility.     

Integral varieties of the canonical cone structure on <Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">P</Emphasis>

The canonical cone structure on a compact Hermitian symmetric space G/P is the fiber bundle where is the cone of the highest weight vectors under the action of the reductive part of P. It is known that the cone coincides with the cone of the vectors tangent to the lines in G/P passing through x, when we consider G/P as a projective variety under its homogeneous embedding into the projective space of the irreducible representation space V of G with highest weight associated to P. A subvariety X of G/P is said to be an integral variety of at all smooth points xG/P. Equivalently, an integral variety of is a subvariety of G/P whose embedded projective tangent space at each smooth point is a linear space We prove a kind of rigidity of the integral varieties under some dimension condition. After making a uniform setting to study the problem, we apply the theory of Lie algebra cohomology as a main tool. Finally we show that the dimension condition is necessary by constructing counterexamples.     

Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205     

Freiling's axioms of symmetry in a general setting and some applications

We formulate C. Freiling's axioms of symmetry for general second-order structures with respect to a certain ideal of small sets contained in them and find several equivalent formulations of the principles. Then we focus on particular models, namely saturated and recursively saturated ones, and show that they are symmetric with respect to appropriate classes of small sets when their second-order part consists of definable sets. Some asymmetric models are also exhibited as well as partial asymmetric ones constructed by forcing. Received: 8 January 1998 / Published online: 21 December 2000     

Parity check matrices and product representations of squares

Let \(N_{\mathbb{F}} \)(n,k,r) denote the maximum number of columns in an n-row matrix with entries in a finite field \(\mathbb{F}\) in which each column has at most r nonzero entries and every k columns are linearly independent over \(\mathbb{F}\). We obtain near-optimal upper bounds for \(N_{\mathbb{F}} \)(n,k,r) in the case k > r. Namely, we show that \(N_\mathbb{F} (n,k,r) \ll n^{\frac{r}{2} + \frac{{cr}}{k}} \) where \(c \approx \frac{4}{3}\) for large k. Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependencies. We present additional applications of this method to a problem on hypergraphs and a problem in combinatorial number theory.     

Likelihood ratio tests of correlated multivariate samples

We develop methods to compare multiple multivariate normally distributed samples which may be correlated. The methods are new in the context that no assumption is made about the correlations among the samples. Three types of null hypotheses are considered: equality of mean vectors, homogeneity of covariance matrices, and equality of both mean vectors and covariance matrices. We demonstrate that the likelihood ratio test statistics have finite-sample distributions that are functions of two independent Wishart variables and dependent on the covariance matrix of the combined multiple populations. Asymptotic calculations show that the likelihood ratio test statistics converge in distribution to central Chi-squared distributions under the null hypotheses regardless of how the populations are correlated. Following these theoretical findings, we propose a resampling procedure for the implementation of the likelihood ratio tests in which no restrictive assumption is imposed on the structures of the covariance matrices. The empirical size and power of the test procedure are investigated for various sample sizes via simulations. Two examples are provided for illustration. The results show good performance of the methods in terms of test validity and power.     

Structural stability of vector fields with shadowing

Let X be a C¹ vector field without singularities. In this paper, we show that X is in the C¹ interior of the set of vector fields with the shadowing property if and only if X satisfies both Axiom A and the strong transversality condition; that is, X is structurally stable.     

A comment on the joint embedding property

The paper presents an alternative proof of the known result that no recursively enumerable number theory has the joint embedding property. Presented at the Conference on Ordered structures and Universal Algebra — in Honor of László Fuchs, Budapest, 1994.     

Asymptotics for estimation and testing procedures under loss of identifiability

Statistical analyses commonly make use of models that suffer from loss of identifiability. In this paper, we address important issues related to the parameter estimation and hypothesis testing in models with loss of identifiability. That is, there are multiple parameter points corresponding to the same true model. We refer the set of these parameter points to as the set of true parameter values. We consider the case where the set of true parameter values is allowed to be very large or even infinite, some parameter values may lie on the boundary of the parameter space, and the data are not necessarily independently and identically distributed. Our results are applicable to a large class of estimators and their related testing statistics derived from optimizing an objective function such as a likelihood. We examine three specific examples: (i) a finite mixture logistic regression model; (ii) stationary ARMA processes; (iii) general quadratic approximation using Hellinger distance. The applications to these examples demonstrate the applicability of our results in a broad range of difficult statistical problems.     

An estimation method for the Neyman chi-square divergence with application to test of hypotheses

We propose a new definition of the Neyman chi-square divergence between distributions. Based on convexity properties and duality, this version of the χ² is well suited both for the classical applications of the χ² for the analysis of contingency tables and for the statistical tests in parametric models, for which it is advocated to be robust against outliers.We present two applications in testing. In the first one, we deal with goodness-of-fit tests for finite and infinite numbers of linear constraints; in the second one, we apply χ²-methodology to parametric testing against contamination.     

Homogeneity tests based on several progressively Type-II censored samples

In this paper, we discuss the problem of testing the homogeneity of several populations when the available data are progressively Type-II censored. Defining for each sample a univariate counting process, we can modify all the methods that were developed during the last two decades (see e.g. [P.K. Andersen, Ø. Borgan, R. Gill, N. Keiding, Statistical Models Based on Counting Processes, Springer, New York, 1993]) for use to this problem. An important aspect of these tests is that they are based on either linear or non-linear functionals of a discrepancy process (DP) based on the comparison of the cumulative hazard rate (chr) estimated from each sample with the chr estimated from the whole sample (viz., the aggregation of all the samples), leading to either linear tests or non-linear tests. Both these kinds of tests suffer from some serious drawbacks. For example, it is difficult to extend non-linear tests to the K-sample situation when K?3. For this reason, we propose here a new class of non-linear tests, based on a chi-square type functional of the DP, that can be applied to the K-sample problem for any K?2.     

A Fubini theorem

Let I₀ be the σ-ideal of subsets of a Polish group generated by Borel sets which have perfectly many pairwise disjoint translates. We prove that a Fubini-type theorem holds between I₀ and the σ-ideals of Haar measure zero sets and of meager sets. We use this result to give a simple proof of a generalization of a theorem of Balcerzak-Ros?anowski-Shelah stating that I₀ on N² strongly violates the countable chain condition.     

Extensions of the conjugate prior through the Kullback-Leibler separators

The conjugate prior for the exponential family, referred to also as the natural conjugate prior, is represented in terms of the Kullback-Leibler separator. This representation permits us to extend the conjugate prior to that for a general family of sampling distributions. Further, by replacing the Kullback-Leibler separator with its dual form, we define another form of a prior, which will be called the mean conjugate prior. Various results on duality between the two conjugate priors are shown. Implications of this approach include richer families of prior distributions induced by a sampling distribution and the empirical Bayes estimation of a high-dimensional mean parameter.     

Analysis of variance and linear contrasts in experimental design with generalized secant hyperbolic distribution

We consider one-way classification model in experimental design when the errors have generalized secant hyperbolic distribution. We obtain efficient and robust estimators for block effects by using the modified maximum likelihood estimation (MML) methodology. A test statistic analogous to the normal-theory F statistic is defined to test block effects. We also define a test statistic for testing linear contrasts. It is shown that test statistics based on MML estimators are efficient and robust. The methodology readily extends to unbalanced designs.