Automata finiteness criterion in terms of van der Put series of automata functions

In the paper we develop the p-adic theory of discrete automata. Every automaton \mathfrakA\mathfrak{A} (transducer) whose input/output alphabets consist of p symbols can be associated to a continuous (in fact, 1-Lipschitz) map from p-adic integers to p-adic integers, the automaton function f_\mathfrakA f_\mathfrak{A} . The p-adic theory (in particular, the p-adic ergodic theory) turned out to be very efficient in a study of properties of automata expressed via properties of automata functions. In the paper we prove a criterion for finiteness of the number of states of automaton in terms of van der Put series of the automaton function. The criterion displays connections between p-adic analysis and the theory of automata sequences.     

An intersection problem for finite automata

A finite automaton with state space S and alphabet A can be thought of as a directed graph with vertex set S such that for each vertex t ϵ S the edges leaving t are in one-to-one correspondence with A. Motivated by a problem in logic, we propose a problem about intersections of languages accepted by finite automata and give some partial results.     

Some applications of propositional logic to cellular automata

In this paper we give a new proof of Richardson's theorem [31]: a global function G_?? of a cellular automaton ?? is injective if and only if the inverse of G_?? is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation from [20]. We also solve two problems regarding complexity of cellular automata formulated by Durand [12] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Syntactic Rings

If the state set and the input set of an automaton are Ω-groups then near-rings are useful in the study of automata (see [5]). These near-rings, called syntactic near-rings, consist of mappings from the state set Q of the automaton into itself. If, as is often the case, Q bears the structure of a module, then the zerosymmetric part N₀(A) of syntactic near-rings is a commutative ring with identity. If N₀(A) is a syntactic ring then its ideals are useful for determining reachability in automata (see [1] or [2]). In this paper we investigate syntactic rings.     

The Automaton Realization of Iterated Wreath Products of Cyclic Groups

We study profinite groups which are infinitely iterated wreath products W _∞ = …?C _{n 2} ?C _{n 1} of finite cyclic groups via combinatorial language of transducers. Namely, we provide a naturally defined automaton realization of the group W _∞ by an automaton over a changing alphabet. Our construction gives a characterization of these profinite groups as automaton groups, i.e. as groups generated by a single automaton.     

Dynamical Systems Associated with Crossed Products

In this paper, we consider both algebraic crossed products of commutative complex algebras A with the integers under an automorphism of A, and Banach algebra crossed products of commutative C ^*-algebras A with the integers under an automorphism of A. We investigate, in particular, connections between algebraic properties of these crossed products and topological properties of naturally associated dynamical systems. For example, we draw conclusions about the ideal structure of the crossed product by investigating the dynamics of such a system. To begin with, we recall results in this direction in the context of an algebraic crossed product and give simplified proofs of generalizations of some of these results. We also investigate new questions, for example about ideal intersection properties of algebras properly between the coefficient algebra A and its commutant A′. Furthermore, we introduce a Banach algebra crossed product and study the relation between the structure of this algebra and the topological dynamics of a naturally associated system.     

A decision procedure for well-formed linear quantum cellular automata

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is O(n²) in the algebraic model of computation if the input automaton has continuous neighborhood. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 381–394 (1997)     

Bass-Tits minimization of automata, quotients of trees and diameters

Let X be a tree and let G=Aut(X), Bass and Tits have given an algorithm to construct the ‘ultimate quotient’ of X by G starting with any quotient of X, an ‘edge-indexed’ graph. Using a sequence of integers that we compute at consecutive steps of the Bass-Tits (BT) algorithm, we give a lower bound on the diameter of the ultimate quotient of a tree by its automorphism group. For a tree X with finite quotient, this gives a lower bound on the minimum number of generators of a uniform X-lattice whose quotient graph coincides with G?X. This also gives a criterion to determine if the ultimate quotient of a tree is infinite. We construct an edge-indexed graph (A,i) for a deterministic finite state automaton and show that the BT algorithm for computing the ultimate quotient of (A,i) coincides with state minimizing algorithm for finite state automata. We obtain a lower bound on the minimum number of states of the minimized automaton. This gives a new proof that language for the word problem in a finitely generated group is regular if and only if the group is finite, and a new proof that the language of the membership problem for a subgroup is regular if and only if the subgroup has finite index.     

Finiteness of U‐rank implies simplicity in homogeneous structures

A (large) superstable homogeneous structure is said to be simple if every complete type over any set A has a free extension over any B ? A. In this paper we give a characterization for this property in terms of U‐rank. As a corollary we get that if the structure has finite U‐rank, then it is simple. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the structure of A/k-bialgebras in prime characteristic

In this paper, we study A/k-bialgebras in prime characteristic. Firstly, we prove a Cartier type structure theorem for cocomplete A/k-bialgebras. Secondly, we generalize Michaelis’s theorem. In particular, we prove that a restricted (k, K)-Lie algebra is proper if and only if its restricted enveloping algebra is proper.     

A note on the rank of semigroups

The rank of a semigroup $\mathcal{A}The rank of a semigroup A\mathcal{A} of functions from a finite set X to X is the minimum of |f(X)| over f ? Af\in \mathcal{A}. Given a finite set X and a subset Y of X, we show that if A\mathcal{A} is a semigroup of functions from X to X and ℬ a transitive semigroup of functions from Y to Y, then the rank of A\mathcal{A} divides that of ℬ provided that f(X)⊆Y for some f ? Af\in \mathcal{A} and that each function in ℬ is the restriction of a function in A\mathcal{A} to Y. To prove this, we generalize a result of Friedman which says that one can partition Y into q subsets of equal weight where q is the rank of ℬ. When one extends a transitive automaton by adding new states and letters, a similar condition guarantees that the rank of the extension divides the original rank.     

Qurves and quivers

In this paper we associate to a -qurve A (formerly known as a quasi-free algebra [J. Cuntz, D. Quillen, Algebra extensions and nonsingularity, J. Amer. Math. Soc. 8 (1995) 251–289] or formally smooth algebra [M. Kontsevich, A. Rosenberg, Noncommutative smooth spaces, math.AG/9812158, 1998]) the one-quiver Q₁(A) and dimension vector α₁(A). This pair contains enough information to reconstruct for all the GL_n-étale local structure of the representation scheme rep_nA. In an appendix we indicate how one might extend this to qurves over non-algebraically closed fields. Further, we classify all finitely generated groups G such that the group algebra kG is a k-qurve. If char(k)=0 these are exactly the virtually free groups. We determine the one-quiver setting in this case and indicate how it can be used to study the finite-dimensional representations of virtually free groups. As this approach also applies to fundamental algebras of graphs of separable k-algebras, we state the results in this more general setting.     

Partition Markov model for multiple processes

In this paper, we analyze the model proposed in García and Londoño¹ in which a set of p-independent sequences of discrete time Markov chains is considered, over a finite alphabet A and with finite order o. The model is obtained identifying the states on the state space A^o where two or more sequences share the same transition probabilities (see also García and González-López²). This identification establishes a partition on {1,…,p}×A^o, the set of sequences, and the state space. We show that by means of the Bayesian information criterion (BIC), the partition can be estimated eventually almost surely. Also, in García and Londoño,¹ it is given a notion of divergence, derived from the BIC, which serves to identify the proximity/discrepancy between elements of {1,…,p}×A^o (see also García et al³). In the present article, we prove that this notion is a metric in the space where the model is built and that it is statistically consistent to determine proximity/discrepancy between the elements of the space {1,…,p}×A^o. We apply the notions discussed here for the construction of a parsimonious model that represents the common stochastic structure of 153 complete genomic Zika sequences, coming from tropical and subtropical regions.     

FINITE-DIMENSIONAL NON-COMMUTATIVE POISSON ALGEBRAS. II

Here is a structure theorem of a finite-dimensional non-commutative Poisson algebra A. A nice element ε of A will be found, so that the Lie module action of an element of a large Poisson subalgebra of A on A is described in terms of ε and the ordinary associative commutator. Consequently, we can figure out a structure of A when the Jacobson radical rad A satisfies (rad A)² = 0. This structure theorem leads us to a classification of the finite-dimensional simple Poisson A-modules.     

Radical of filters in BL‐algebras

In this paper, the notion of the radical of a filter in BL‐algebras is defined and several characterizations of the radical of a filter are given. Also we prove that A/F is an MV‐algebra if and only if D_s(A) ? F. After that we define the notion of semi maximal filter in BL‐algebras and we state and prove some theorems which determine the relationship between this notion and the other types of filters of a BL‐algebra. Moreover, we prove that A/F is a semi simple BL‐algebra if and only if F is a semi maximal filter of A. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

The minimal polynomial of a matrix ∗

Let Rbe a finite dimensional central simple algebra over a field F A be any n× n matrix over R. By using the method of matrix representation, this paper obtains the structure formula of the minimal polynomial q_A (λ) of A over F. By using q_A (λ), this paper discusses the structure of right (left) eigenvalues set of A, and obtains the necessary and sufficient condition that a matrix over a finite dimensional central division algebra is similar to a diagonal matrix.     

Generic modules over the quantum groupU t (sl(2)) att a root of unit

LetA be a finite dimensionalk-algebra, an indecomposable (left)A-moduleM is called generic providedM is infinitek-dimensional but finite length as (right) End _A M-module. In this paper we given the explicit structure of generic modules and their endomorphism rings over the finite dimensional quantum groupU _t (sl(2)) att being a root of unit.     

On Partial Classes Containig All Monotone and Zero-Preserving Total Boolean Functions

We describe sets of partial Boolean functions being closed under the operations of superposition. For any class A of total functions we define the set ??(A) consisting of all partial classes which contain precisely the functions of A as total functions. The cardinalities of such sets ??(A) can be finite or infinite. We state some general results on ??(A). In particular, we describe all 30 closed sets of partial Boolean functions which contain all monotone and zero-preserving total Boolean functions.     

Typical representations for orthosymplectic lie superalgebras

In this paper we extend the study of the prime ideal structure of group rings initiated by Gilmer (1974), Brewer-Costa-Lady (1975), and Anderson-Bouvier-Dobbs-Fontana-Kabbaj (1988). Of particular inter-est is the transfer from A to A[G] of certain properties which are linked to the prime spectrum such as S-domain or Jaffard domain. Their study will follow the same lines as the usual approach to the study of prime ideal structure in polynomial rings.     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.