Search

Motivated by the analysis of neural net models between integer and rational weights, we introduce a so-called cut language over a real digit alphabet, which contains finite β-expansions (i.e. base-β representations) of the numbers less than a given threshold. We say that an infinite β-expansion is eventually quasi-periodic if its tail sequence formed by the numbers whose representations are obtained by removing leading digits, contains an infinite constant subsequence. We prove that a cut language is regular iff its threshold is a quasi-periodic number whose all β-expansions are eventually quasi-periodic, by showing that altogether they have a finite number of tail values. For algebraic bases β, we prove that there is an eventually quasi-periodic β-expansion with an infinite number of tail values iff there is a conjugate of β on the unit circle. For transcendental β combined with algebraic digits, a β-expansion is eventually quasi-periodic iff it has a finite number of tail values. For a Pisot base β and digits from the smallest field extension Q ( β ) over rational numbers including β, we show that any number from Q ( β ) is quasi-periodic. In addition, we achieve a dichotomy that a cut language is either regular or non-context-free and we show that any cut language with rational parameters is context-sensitive.

The linear- or affine-invariance is the property of a function family that is closed under linear- or affine-transformations on the domain, and closed under linear combinations of functions, respectively. Both the linear- and affine-invariant families of functions are generalizations of many symmetric families, for instance, the low degree polynomials. Kaufman and Sudan (2007) [21] introduced the notions of ''constraint'' and ''characterization'' to characterize the locally testable affine- and linear-invariant families of functions over finite fields of constant size. In this article, it is shown that, for any finite field F of size q and characteristic p, and its arbitrary extension field K of size Q, if an affine-invariant family @?@?{K^n->F} has a k-local constraint, then it is k^'-locally testable for k^'=k^2^Q^pQ^2^Q^p^+^4; and that if a linear-invariant family @?@?{K^n->F} has a k-local characterization, then it is k^'-locally testable for k^'=2k^2^Q^pQ^4^(^Q^p^+^1^). Consequently, for any prime field F of size q, any positive integer k, we have that for any affine-invariant family @? over field F, the four notions of ''the constraint'', ''the characterization'', ''the formal characterization'' and ''the local testability'' are equivalent modulo a poly(k,q) of the corresponding localities; and that for any linear-invariant family, the notions of ''the characterization'', ''the formal characterization'' and ''the local testability'' are equivalent modulo a poly(k,q) of the corresponding localities. The results significantly improve, and are in contrast to the characterizations in [21], which have locality exponential in Q, even if the field K is prime. In the research above, a missing result is a characterization of linear-invariant function families by the more natural notion of constraint. For this, we show that a single strong local constraint is sufficient to characterize the local testability of a linear-invariant Boolean function family, and that for any finite field F of size q greater than 2, there exists a linear-invariant function family @? over F such that it has a strong 2-local constraint, but is not q^d^q^-^1^-^1-locally testable. The proof for this result provides an appealing approach toward more negative results in the theme of characterization of locally testable algebraic properties, which is rare, and of course, significant.

Let @S be an alphabet of size t, let f:@S^*->@S^* be a non-erasing morphism, let w be an infinite fixed point of f, and let E(w) be the critical exponent of w. We prove that if E(w) is finite, then for a uniform f it is rational, and for a non-uniform f it lies in the field extension Q[r,@l"1,...,@l"@?], where r,@l"1,...,@l"@? are the eigenvalues of the incidence matrix of f. In particular, E(w) is algebraic of degree at most t. Under certain conditions, our proof implies an algorithm for computing E(w).

From an interpolation method on algebraic curves, due to D.V. Chudnovsky and G.V. Chudnovsky, we give a new method for the construction of bilinear algorithms for multiplication in the extensions of finite fields. We obtain algorithms better than known ones.

Combinatory differential fields arise if differential fields are augmented by operations which allow functions that are programmable in the usual recursive sense to be denoted. The present paper defines this concept. It is shown that every differential field whose field of constants is ordered can be extended to a combinatory field. We generalize the basic notions of the Liouville-Ritt-Risch theory of closed-form solvability to combinatory field extensions and present some explorative examples of problems and solutions. —Author's Abstract