On cellular automata over Galois rings

In this paper we study the invertibility of one-dimensional cellular automata, determined by a local rule, acting on the space of all doubly-infinite sequences taking values in a finite Galois ring. We also compute the topological entropy of one-dimensional CA generated by additive local rule over a finite Galois ring. We conclude by showing that the topological entropy of an additive invertible CA over a finite Galois ring is equal to its inverse.     

Comments on pole assignability over rings

We observe that the proof by Eising of the pole assignment theorem for linear systems over a principal ideal domain [4] actually remains valid for any elementary divisor ring. For large classes of rings matrix characterizations of pole assignability are given.     

Pole assignment for systems over rings

A very simple proof of the pole assignment theorem for systems over a principal ideal domain (and other rings) is given. Furthermore, an algorithm is presented. Extensions are also indicated.     

Strong feedback cyclization for systems over rings

For nonnecessarily reachable systems over a commutative ring R, we define a strong form of feedback cyclization (FC). With this natural generalization of the FC property we obtain a feedback reduced form for systems over strong FC rings (i.e. rings for which every system verifies the FC property). In the particular case of reachable single input systems, this gives the usual control canonical form of Bumby et al. [Remarks on the pole-shifting problem over rings, J. Pure Appl. Algebra 20 (1981) 113–127]. Also it is proved that a commutative ring with 1 in its stable range has the strong FC property if and only if it has the UCU property, which is the natural parallel form of the result given by Brewer et al. [Pole assignability in polynomial rings, power series rings and Prüfer domains, J. Algebra 106 (1987) 265–286] for the reachable case. Many classes of rings which were known to be FC rings are in fact strong FC rings, but there are FC rings which are not strong FC rings.     

Learning Matrix Functions over Rings

Let R be a commutative Artinian ring with identity and let X be a finite subset of R . We present an exact learning algorithm with a polynomial query complexity for the class of functions representable as f(x) = Π _i=1 ⁿ A _i (x _i ), where, for each 1 ≤ i ≤ n , A _i is a mapping A _i : X → R ^{mi× mi+1} and m ₁ = m _n+1 = 1 . We show that the above algorithm implies the following results: 1. Multivariate polynomials over a finite commutative ring with identity are learnable using equivalence and substitution queries. 2. Bounded degree multivariate polynomials over Z _n can be interpolated using substitution queries. 3. The class of constant depth circuits that consist of bounded fan-in MOD gates, where the modulus are prime powers of some fixed prime, is learnable using equivalence and substitution queries. Our approach uses a decision tree representation for the hypothesis class which takes advantage of linear dependencies. This paper generalizes the learning algorithm for automata over fields given in [BBB+]. Received January 28, 1997; revised May 29, 1997, June 18, 1997, and June 26, 1997.     

Singular shift registers over residue class rings

The study of shift registers over the ringZ _p ^r (p a prime,r 1), in particular the singular case, is carried out, giving necessary and sufficient conditions to make a shift register singular. Its state graph is characterized as a tree, whose form depends on the characteristic polynomial of the shift register. The relationships with singular shift register overZ _p are explored and a proof of their equivalence is presented.Research sponsored by the National Science Foundation, Grant GK-1065x, and the Joint Services Electronics Program, Grant AFOSR-68-1488.Part of this work was done while the author was at Electronics Research Laboratory, University of California at Berkeley.     

Invertibility of linear dynamical systems over commutative rings

This correspondence is addressed to the question of invertibility of linear dynamical systems. Specifically, inversion over principal ideal domains is discussed in view of the fact that 2-D systems can be considered as 1-D systems over a principal ideal domain.     

The Sylvester resultant with applications to systems over rings

The Sylvester resultant is studied in this paper for systems over rings. The systems over rings may have zero coprime fractions, fractor coprime fractions, and fraction with common factors. The Sylvester resultant can be used to test these situations. It can also be used to achieve the design of coefficient assignment in the first case, to test the regulability in the second case, and to find the fractor coprime fractions in the third case.     

Algorithms for solving systems of linear diophantine equations in residue rings

Algorithms are proposed that construct the basis of the set of solutions to a system of homogeneous or inhomogeneous linear Diophantine equations in a residue ring modulo n when the prime factors of n are known. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 27–40, November–December 2007.     

Computing minimal associated primes in polynomial rings over the integers

An algorithm is presented to compute the minimal associated primes of an ideal in a polynomial ring over the integers. It differs from the known algorithms insofar as it avoids having to compute Gröbner bases over the integers until the very end, thereby eliminating one of the bottlenecks of those algorithms.     

Regulation of linear systems over rings by dynamic output feedback

A general algebraic solution to the problem of regulation of linear systems over arbitrary commutative rings by dynamic output feedback is given which extends the theory of regulation for such systems. Furthermore, the notion of row (column) regularity for polynomial matrices over a class of rings (Bezout domains) is introduced. This concept is shown to simplify the regulation problem considerably for these rings compared to the general case.     

The lattice of minimal realizations of response maps over rings

A lattice characterization is given for the class of minimal-rank realizations of a linear response map defined over a (commutative) Noetherian integral domain. As a corollary, it is proved that there are only finitely many nonisomorphic minimal-rank realizations of a response map over the integers, while for delay-differential systems these are classified by a lattice of subspaces of a finite-dimensional real vector space.This research was supported in part by US Army Research Grant DA-ARO-D-31-124-72-G114 and by US Air Force Grant 72-2268 through the Center for Mathematical System Theory, University of Flroida, Gainesville, FL 32611, USA.     

Inapproximability results for equations over finite groups

An equation over a finite group G is an expression of form w₁w₂…w_k=1_G, where each w_i is a variable, an inverted variable, or a constant from G; such an equation is satisfiable if there is a setting of the variables to values in G so that the equality is realized. We study the problem of simultaneously satisfying a family of equations over a finite group G and show that it is NP-hard to approximate the number of simultaneously satisfiable equations to within |G|−ε for any ε>0. This generalizes results of Håstad (J. ACM 48 (4) (2001) 798), who established similar bounds under the added condition that the group G is Abelian.     

Analysis of nonlinear time-delay systems using modules over non-commutative rings

The theory of non-commutative rings is introduced to provide a basis for the study of nonlinear control systems with time delays. The left Ore ring of non-commutative polynomials defined over the field of meromorphic function is suggested as the framework for such a study. This approach is then generalized to a broader class of nonlinear systems with delays that are called generalized Roesser systems. Finally, the theory is applied to analyze nonlinear time-delay systems. A weak observability is defined and characterized, generalizing the well-known linear result. Properties of closed submodules are then developed to obtain a result on the accessibility of such systems.     

New quantum codes from dual-containing cyclic codes over finite rings

Let \(R=\mathbb {F}_{2^{m}}+u\mathbb {F}_{2^{m}}+\cdots +u^{k}\mathbb {F}_{2^{m}}\), where \(\mathbb {F}_{2^{m}}\) is the finite field with \(2^{m}\) elements, m is a positive integer, and u is an indeterminate with \(u^{k+1}=0.\) In this paper, we propose the constructions of two new families of quantum codes obtained from dual-containing cyclic codes of odd length over R. A new Gray map over R is defined, and a sufficient and necessary condition for the existence of dual-containing cyclic codes over R is given. A new family of \(2^{m}\)-ary quantum codes is obtained via the Gray map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R. In particular, a new family of binary quantum codes is obtained via the Gray map, the trace map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R.