Isomorphism of subshifts is a universal countable borel equivalence relation

We use the theory of Borel equivalence relations to analyze the equivalence relation of isomorphism among one-dimensional subshifts. We show that this equivalence relation is a universal countable Borel equivalence relation, so that it admits no definable complete invariants fundamentally simpler than the equivalence classes. We also see that the classification of higher dimensional subshifts up to isomorphism has the same complexity as for the one-dimensional case.     

The Myhill property for strongly irreducible subshifts over amenable groups

Let G be an amenable group and let A be a finite set. We prove that if X ? A ^G is a strongly irreducible subshift then X has the Myhill property, that is, every pre-injective cellular automaton ?? : X ?? X is surjective.     

Orbit equivalence,flow equivalence and ordered cohomology

We study self-homeomorphisms of zero dimensional metrizable compact Hausdorff spaces by means of the ordered first cohomology group, particularly in the light of the recent work of Giordano Putnam, and Skau on minimal homeomorphisms. We show that flow equivalence of systems is analogous to Morita equivalence between algebras, and this is reflected in the ordered cohomology group. We show that the ordered cohomology group is a complete invariant for flow equivalence between irreducible shifts of finite type; it follows that orbit equivalence implies flow equivalence for this class of systems. The cohomology group is the (pre-ordered) Grothendieck group of the C^*-algebra crossed product, and we can decide when the pre-ordering is an ordering, in terms of dynamical properties.     

A certain finiteness property of Pisot number systems

In the study of substitutative dynamical systems and Pisot number systems, an algebraic condition, which we call ‘weak finiteness’, plays a fundamental role. It is expected that all Pisot numbers would have this property. In this paper, we prove some basic facts about ‘weak finiteness’. We show that this property is valid for cubic Pisot units and for Pisot numbers of higher degree under a dominant condition.     

On the equivalence of certain quasi-Hermitian varieties

By Aguglia et al., new quasi-Hermitian varieties ${\mathrm{ℳ}}_{\alpha ,\beta }$ in $\text{PG}\left(r,q^2\right)$ depending on a pair of parameters $\alpha ,\beta$ from the underlying field $\text{GF}\left(q^2\right)$ have been constructed. In the present paper we study the structure of the lines contained in ${\mathrm{ℳ}}_{\alpha ,\beta }$ and consequently determine the projective equivalence classes of such varieties for $q$ odd and $r=3$. As a byproduct, we also prove that the collinearity graph of ${\mathrm{ℳ}}_{\alpha ,\beta }$ is connected with diameter 3 for $q\equiv 1\left(\mathrm{mod}4\right)$.     

A property of certain multistage linear programs and some applications

In this paper, we present a property of certain linear multistage problems. To solve them, a method which takes this property into account is presented. It requires the resolution of 2N–1 subproblems, if there areN stages in the original problem. A sufficient condition is given on the matrix of the constraints for the property to be true. When only a submatrix has this property, we propose to use the Dantzig-Wolfe decomposition principle. We then can solve the subproblem with the proposed method. Applications to linear and nonlinear programming are presented.This work was done while the author was Visiting Scholar at the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California.     

A characterization of subshifts with bounded powers

We consider minimal, aperiodic symbolic subshifts and show how to characterize the combinatorial property of bounded powers by means of a metric property. For this purpose we construct a family of graphs which all approximate the subshift space, and define a metric on each graph, which extends to a metric on the subshift space. The characterization of bounded powers is then given by the Lipschitz equivalence of a suitably defined infimum metric with the corresponding supremum metric. We also introduce zeta-functions and relate their abscissa of convergence to various exponents of complexity of the subshift. Our results, following a previous work of two of the authors, are based on constructions in non commutative geometry.     

Surface subshifts and subshift data

This paper is concerned with Smale diffeomorphisms on compact oriented surfaces. We determine with which genus a closed oriented surface can carry a Smale diffeomorphism associated with a subshift of finite type corresponding to a given reciprocal polynomial with constant term one, and determine what a combination of subshifts and period imformations of sinks and sources can be realized on a given oriented surface by a Smale diffeomorphism in a definite isotopic class. Necessary and sufficient conditions are given.This is a part of my Ph.D. thesis.     

The equivalence of certain equidistant binary codes and symmetric bibds

We study equidistant codes of length 4k + 1 having (constant) weight 2k, and (constant) distance 2k between codewords. The maximum number of codewords is 4k; this can be attained if and only ifk = (u ² +u)/2 (for some integeru) and there exists a ((2u ² + 2u + 1,u ², (u ² −u)/2) — SBIBD. Also, one can construct such a code, with 4k − 1 codewords, from a (4k − 1, 2k − 1,k − 1) — SBIBD. Supported, in part by NSERC grants U0217 (D. R. Stinson), A3558 (G. H. J. van Rees).     

The equivalence of certain heat kernel and Green function bounds

We show that certain upper and lower bounds on the Green function and heat kernel of a second-order elliptic operator in a bounded region are equivalent, and imply a number of apparently stronger bounds. We also show that these bounds are equivalent to the Harnack inequality except for peculiar regions, and are therefore almost always valid.     

Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts

For a pseudovariety of ordered semigroups, let be the class of sofic subshifts whose syntactic semigroup lies in . It is proved that if contains then is closed under taking shift equivalent subshifts, and conversely, if is closed under taking conjugate subshifts then contains and . Almost finite type subshifts are characterized as the irreducible elements of , which gives a new proof that the class of almost finite type subshifts is closed under taking shift equivalent subshifts.