The basis automaton for the given regular language

A new problem of the theory of finite automata (Rabin-Scott’s automata) is considered. So called basis automaton for the given regular languageL is defined. This automaton is unique for the givenL, it is defined by two automata of canonical form: forL and for its inverse languageL ^R. Some properties of basis automata are considered. Such properties make these automata most convenient for using in some special tasks, dealing with the given regular language.     

A note on the finite basis and finite rank properties for pseudovarieties of semigroups

The finite basis property is often connected with the finite rank property, which it entails. Many examples have been produced of finite rank varieties which are not finitely based. In this note, we establish a result on nilpotent pseudovarieties which yields many similar examples in the realm of pseudovarieties of semigroups.     

Some properties of skew codes over finite fields

After recalling the definition of some codes as modules over skew polynomial rings, whose multiplication is defined by using an endomorphism and a derivation, and some basic facts about them, in the first part of this paper we study some of their main algebraic and geometric properties. Finally, for module skew codes constructed only with an automorphism, we give some BCH type lower bounds for their minimum distance.     

Recognition of certain properties of automaton algebras

Abstract. The paper considers a new algebraic object, the completely automaton binomial algebras, which generalize certain existing classes of algebras. The author presents a classification of semigroup algebras taking into account completely automaton algebras and gives the corresponding examples. A number of standard algorithmic problems are solved for completely automaton binomial algebras: the recognition of a strict and nonstrict polynomial property, the recognition of the right and/or left finite processing, and the construction of the determining regular language for an algebra with finite processing and for monomial subalgebras of a free associative algebra and certain completely automaton algebras. For an automaton monomial algebra, the author constructs the left syzygy module of a finite system of elements and the Gröbner basis of a finitely generated left ideal; also, some algorithmic problems are solved.     

Some geometric properties of metric ultraproducts of finite simple groups

In this article we prove some previously announced results about metric ultraproducts of finite simple groups. We show that any non-discrete metric ultraproduct of alternating or special linear groups is a geodesic metric space. For more general non-discrete metric ultraproducts of finite simple groups, we are able to establish path-connectedness. As expected, these global properties reflect asymptotic properties of various families of finite simple groups.     

Fuzzy正则表达式与Fuzzy有限态自动机的关系

首先给出了Fuzzy正则表达式的定义,接着通过研究Fuzzy正则表达式与Fuzzy有限态自动机的关系,得到了两个重要性质,即：每一个Fuzzy正则表达式,都有一个非确定性的Fuzzy有限态自动机接受其代表的语言;每一个被确定性的Fuzzy有限态自动机接受的语言,都能被一个Fuzzy正则表达式表示．     

幺半环上模糊有限状态机的一些性质

状态机的很多性质在计算机等方面有着广泛的应用,因此对状态机的研究具有重要的意义.本文给出了幺半环上模糊有限状态机的概念,对状态之间的等价进行了定义,引入了同态的概念,得到同态定理和满同态分解定理,讨论了幺半环上模糊有限状态机在同态下的交换性质和连通性以及子状态机的可分离性.     

Possible edges of a finite automaton defining a given regular language

In this paper we consider non-deterministic finite Rabin-Scott’s automata. We define special abstract objects, being pairs of values of states-marking functions. On the basis of these objects as the states of automaton, we define its edges; the obtained structure is considered also as a non-deterministic automaton. We prove, that any edge of any non-deterministic automaton defining the given regular language can be obtained by such techniques. Such structure can be used for solving various problems in the frames of finite automata theory.     

Some properties of the basis invariants of the unitary group W(K5)

The basis invariants of degrees 6, 12, and 18 of the unitary groupW(K ₅) are constructed in explicit form by a new method.Translated from Ukrainskií Geometricheskií Sbornik, No. 30, 1987, pp. 92–96.     

Influence of the topology of a cellular automaton on its dynamical properties

Notwithstanding the numerous scientific efforts that have been spent to unravel the dynamics of cellular automata (CA), there is still only fragmented and incomplete knowledge of the interference that possibly exists between a CA’s dynamical properties in general and its stability in particular, on the one hand, and the whole of its spatial entities and their interconnection, referred to as a CA’s topology, on the other hand. Since a clear understanding of this interference is unbearable to fully comprehend the dynamics of CA, this paper is devoted to a quantitative assessment of this interference. More precisely, after pinning down the so-called representative tessellation size (RTS), it is verified to what extent the input sensitivity of 2-state CA and their stability depends on the characteristics of their topology. Therefore, 12 random graphs having six different vertex degree distributions (VDDs) are used to embody the CA’s topology and to verify how their dynamics is affected by the specificities of these graphs. It is found that the RTS is 400. Further, the interference is strongest with regard to the CA’s stability to the extent that the classification of CA into behavioral classes can be seriously affected by the choice of the VDD.     

Construction of basis functions in the finite element method

In many applications of the finite element method, the explicit form of the basis functions is not known. A well-known exception is that of piecewise linear approximation over a triangulation of the plane, where the basis functions are pyramid functions. In the present paper, the basis functions are displayed in closed form for piecewise polynomial approximation of degreen over a triangulation of the plane. These basis functions are expressed simply in terms of the pyramid functions for linear approximation.     

On finite completely simple semigroups having no finite basis of identities

The purpose of this note is to provide a correct proof of the fact that there exist finite completely simple semigroups having no finite basis of identities.     

Congruence meet-semidistributive locally finite varieties and a finite basis theorem

We provide several conditions that, among locally finite varieties, characterize congruence meet-semidistributivity and we use these conditions to give a new proof of a finite basis theorem published by Baker, McNulty, and Wang in 2004. This finite basis theorem extends Willard’s Finite Basis Theorem.     

A finite basis theorem for quasivarieties

We consider varieties with the property that the intersection of any pair of principal congruences is finitely generated, and, in fact, generated by pairs of terms constructed from the generators of the principal components in a uniform way. We say that varieties with this property haveequationally definable principal meets (EDPM). There are many examples of these varieties occurring in the literature, especially in connection with metalogical investigations. The main result of this paper is that every finite, subdirectly irreducible member of a variety with EDPM generates a finitely based quasivariety. This is proved in Section 2. In the first section we prove that every variety with EDPM is congruence-distributive.Presented by George Gratzer.