Mortality problem and affine automata

The mortality problem for 2×2 matrices is treated from the automata theory viewpoint. This problem is shown to be closely related to the reachability problem for linear and affine automata of low dimensions. The decidability of the reachability problem is proved for some subclasses of one-dimensional affine automata. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 24–29, March–April 2008.     

Equivalence of two-dimensional multitape automata

The equivalence of multitape automata with multi-dimensional tapes is considered. Their heads move monotonically in all directions (their backward movement is impossible). The special case when the dimensions of tapes are less than or equal to 2 is proved to be solvable. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 3–10, January–February 2008.     

On the Height of a Finite Automaton

The states of a finite automaton are ordered by height. This order is shown to be graduated, and the well-known Cerny problem on the minimal length of reset words can be formulated in terms of global height. The problem is proved for automata with four states.     

Analyzing the structure of a class of linear automata over a ring $$ Z_{p^k } $$

Basic finite-automaton characteristics are established for the class of all linear automata and information-lossless automata over a ring. The complexities of solving problems of parametric identification and initial-state identification are analyzed. The sets of fixed points for mappings realized by initial automata are characterized. Canonical forms are proposed for linear automata over the ring. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 60–74, May–June 2008.     

论有穷状态验证方法的局限性

程序有穷状态验证方法是介于程序验证和程序测试之间的一种方法，一方面它如同程序验证一样可以证明某程序具有某些要求的性质，或找出反例证明该程序不具有所要求的性质。另一方面它又不像程序验证那样复杂，要求验证人员具有较高的形式化推理的专业理论和数学水平。但是，现有的有穷状态验证方法有很大的局限性，它要求所论证的性质是有穷自动机所接受的事件序列的集合，或等价地说该性质能表示成为正则表达式。众所周知，有穷自动机所能接受的语言类，按Chomsky字的集合的分类是很小的类。本文讨论了这种局限性，井尝试突破只能使用有穷自动机的限制，提出了一种新的验证方法——有穷路径验证法。在这种方法中，所论证的性质表示可以推广到使用任何一类自动机。作为代价，描写系统的模型限制是无环的。对于有环的描写系统的模型，本文提出了一种称之为“有穷路径测试”的方法。同一般的程序测试一样，用这种方法通过测试不能正面地验证程序的正确性，可是如果通不过测试，则能帮你发现反例，找出程序的错误。与一般的程序测试不同的是这里的测试是相对于模型的路径，而不执行实际的程序。     

有限布尔代数上的线性自动机

自动机理论是计算机科学理论的重要组成部分。论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机。定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件。     

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata are discussed. The notions of intuitionistic fuzzy recognizer, complete accessible intuitionistic fuzzy recognizer, intuitionistic fuzzy finite automata, deterministic intuitionistic fuzzy finite automata, and intuitionistic fuzzy language are introduced. It is shown that the languages recognized by intuitionistic fuzzy recognizer are regular, and the intuitionistic fuzzy languages recognized by the intuitionistic fuzzy finite automaton and the intuitionistic fuzzy languages recognized by deterministic intuitionistic fuzzy finite automaton are equivalent. This work is supported by National Science Foundation of China (Grant No.10571112), “TRAPOYT” of China and National 973 Foundation Research Program(Grant No.2002CB312200).     

Cyclic Check Experiments with Group Automata

A characterization of a cyclic check experiment for a reduced connected finite group automaton is found relative to the class of all the reduced connected finite group automata. On this basis, an algorithm for construction of a cyclic check experiment is proposed. Exact estimates of the multiplicity and minimum length of such an experiment are found. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 32–46, May–June 2005.     

Experiments with automata when the upper bound of the number of their states is unknown

The properties of a class of initial finite automata are investigated; the class is possibly infinite, and each input-output signal of a fixed set of automata from this class is produced by no more than one state. The exact finiteness conditions of this class and its important subclasses and exact existence conditions of check experiments related to these classes are found. The existence conditions of experiments on recognition of such automata are also described. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 59–71, July–August, 1999.     

A relationship between Turing machines and finite automata on four-dimensional input tapes

Due to the advances in computer animation, motion image processing, virtual reality systems, and so forth recently, it is useful for analyzing computation of multi-dimensional information processing to explicate the properties of four-dimensional automata. From this point of view, we first proposed four-dimensional automata in 2002, and investigated their several accepting powers. In this paper, we coutinue the study, and mainly concentrate on investigating the relationship between the accepting powers of four-dimensional finite automata and seven-way four-dimensional tape-bounded Turing Machines. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

On characteristic sets and degrees of finite automata

The characteristic sets and degrees of finite automata are notions used by Biermann for his finite automaton learner. Some fundamental properties and relations of these notions are considered. A necessary and sufficient condition under which his learner converges to an expected automaton is given.     

A software system for growth analysis of mealy automata

A software system for the growth analysis of Mealy automata during iterations is discussed. The mathematical basis of the system is described. The main difficulties arising during the analysis are studied. The structure and software implementation of the system are described. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 125–141, March–April 2006.     

Equivalence of regular expressions over a partially commutative alphabet

The equivalence problem is considered for regular expressions over a partially commutative alphabet. The alphabet is decomposed into disjoint subsets of noncommutative elements. The special case of the problem when the cardinal number of only one subset is larger than 1 and the cardinal numbers of the other subsets are equal to 1 is proved to be algorithmically solvable. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 65–74, May–June 2009.     

Estimation of the length of reset words for automata with simple idempotents

A quadratic upper bound on the length of a minimal reset word is obtained for finite automata with simple idempotents. Each input symbol of the automata considered induces a transformation that is an idempotent with the unit defect or a bijection on the set of states. This bound is only twice as large as the well-known lower bound of this length. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 32–39, May–June, 2000.     

Determinization of weighted finite automata over strong bimonoids

We consider weighted finite automata over strong bimonoids, where these weight structures can be considered as semirings which might lack distributivity. Then, in general, the well-known run semantics, initial algebra semantics, and transition semantics of an automaton are different. We prove an algebraic characterization for the initial algebra semantics in terms of stable finitely generated submonoids. Moreover, for a given weighted finite automaton we construct the Nerode automaton and Myhill automaton, both being crisp-deterministic, which are equivalent to the original automaton with respect to the initial algebra semantics, respectively, the transition semantics. We prove necessary and sufficient conditions under which the Nerode automaton and the Myhill automaton are finite, and we provide efficient algorithms for their construction. Also, for a given weighted finite automaton, we show sufficient conditions under which a given weighted finite automaton can be determinized preserving its run semantics.     

Two types of nonlinear automata over a finite ring

The structure of a class of automata is analyzed. These automata are analogs of symmetric chaotic dynamical systems over a finite ring, namely, the Guckenheimer–Holmes cycle and free-running systems. Problems of parametric identification and identification of initial states are solved, and a set of fixed points of automaton mappings is characterized. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 57–68, July–August 2009.     

Path-bounded three-dimensional finite automata

The comparative study of the computational powers of deterministic and nondeterministic computations is one of the central tasks in complexity theory. This paper investigates the computational power of nondeterministic computing devices with restricted nondeterminism. There are only few results measuring the computational power of restricted nondeterminism. In general, there are three possibilities to measure the amount of nondeterminism in computation. In this paper, we consider the possibility to count the number of different nondeterministic computation paths on any input. In particular, we deal with five-way three-dimensional finite automata with multiple input heads operating on three-dimensional input tapes. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Systems of generators of automaton permutations groups

Systems of induced generating actions of automaton permutations groups on words of length r are investigated. A family of irreducible systems of generators is constructed, and the cardinality of such systems is found to be related with r. The infinite generativity (even in the topological sense) of groups of all automaton permutations, finite automaton permutations, and finitary automaton permutations is established; the well-known proof of this fact contained an error. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 121–133, May–June, 2000.     

Nonlinear automata over a finite ring

The properties of the class of information-lossless automata represented by recurrent relations over a finite ring are investigated. For these automata, the structure of classes of equivalent states is investigated, problems of parametric identification and identification of the initial state are solved, and the variation in the behavior of such automata as a result of variation of their parameters or initial states is characterized. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 29–42, November–December 2006.     

An improved algorithm for determinization of weighted and fuzzy automata

For a given weighted finite automaton over a strong bimonoid we construct its reduced Nerode automaton, which is crisp-deterministic and equivalent to the original weighted automaton with respect to the initial algebra semantics. We show that the reduced Nerode automaton is even smaller than the Nerode automaton, which was previously used in determinization related to this semantics. We determine necessary and sufficient conditions under which the reduced Nerode automaton is finite and provide an efficient algorithm which computes the reduced Nerode automaton whenever it is finite. In determinization of weighted finite automata over semirings and fuzzy finite automata over lattice-ordered monoids this algorithm gives smaller crisp-deterministic automata than any other known determinization algorithm.