Maximum ease of testability of logic circuits with respect to multiple stuck-on faults

A synthesis method is proposed for an arbitrary abstract finite automaton which is checked by a test of a small fixed volume (35 bits). The test detects multiple faults that are not self-corrected by the circuit.Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 49–57, January–February, 1992.     

The dynamics of digital circuits with memory for ternary signals

The paper examines a digital automaton with memory operating in the ternary alphabet (0, 1, ). The problem of analytical determination of ternary processes on automaton outputs and inside the automaton from given ternary processes on the automaton inputs is considered. An algorithm is proposed reducing this problem to standard determination of the processes in an automaton with the alphabet (0, 1).Translated from Kibernetika, No. 4, pp. 19–25, July–August, 1989.     

Interacting automata

Compatibility of interacting partial nondeterministic automata is defined. Two interacting automata are compatible if an input signal from one automaton always induces a defined transition in the other automaton.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 17–29, November–December, 1991.     

Software reliability analysis and choice of software reliability criteria

Functional reliability of computer software is considered using fuzzy automaton representation of software systems.Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 46–60, March–April, 1992.     

Saa machine

An application of Glushkov's abstract computer model is proposed. The control automaton of this model is implemented in the form of an interpreting automaton-a SAA machineTranslated from Kibernetika, No. 6, pp. 83–87, November–December, 1989.     

Using Knowledge-Based Neural Networks to Improve Algorithms: Refining the Chou–Fasman Algorithm for Protein Folding

This article describes a connectionist method for refining algorithms represented as generalized finite-state automata. The method translates the rule-like knowledge in an automaton into a corresponding artificial neural network, and then refines the reformulated automaton by applying backpropagation to a set of examples. This technique for translating an automaton into a network extends the KBANN algorithm, a system that translates a set of prepositional rules into a corresponding neural network. The extended system, FSKBANN, allows one to refine the large class of algorithms that can be represented as state-based processes. As a test, FSKBANN is used to improve the Chou–Fasman algorithm, a method for predicting how globular proteins fold. Empirical evidence shows that the multistrategy approach of FSKBANN leads to a statistically-significantly, more accurate solution than both the original Chou–Fasman algorithm and a neural network trained using the standard approach. Extensive statistics report the types of errors made by the Chou–Fasman algorithm, the standard neural network, and the FSKBANN network.     

Rank of a finite automaton

The notion of rank of a finite automaton is considered. The Cerny—Pin conjecture about the length of terminal words in finite abstract automata is generalized to linear automata.Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 3–10, May–June, 1992.     

Tableau-based automata construction for dynamic linear time temporal logic*

We present a tableau-based algorithm for obtaining a Büchi automaton from a formula in Dynamic Linear Time Temporal Logic (DLTL), a logic which extends LTL by indexing the until operator with regular programs. The construction of the states of the automaton is similar to the standard construction for LTL, but a different technique must be used to verify the fulfillment of until formulas. The resulting automaton is a Büchi automaton rather than a generalized one. The construction can be done on-the-fly, while checking for the emptiness of the automaton. We also extend the construction to the Product Version of DLTL.*This research has been partially supported by the project MIUR PRIN 2005 ‘Specification and verification of agent interaction protocols’.     

Complexity and structure of microprogrammed and nanoprogrammed automata realizing cyclograms

Microprogrammed and nanoprogrammed automata with programmable microinstructions are considered. Their software and hardware complexity is estimated as a function of cyclogram parameters. Some suggestions for choosing the automaton structure are advanced.Translated from Kibernetika, No. 5, pp. 97–103, 111, September–October, 1990.     

Language recognition by two-way deterministic pushdown automata

It is proved that any bounded context-free language can be recognized by a two-way deterministic automaton with a finite-rotary counter.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 177–181, November–December 2004.This revised version was published online in April 2005 with a corrected cover date.     

Logical methods to obtain deterministic reliability estimates for systems

We consider the construction of deterministic integral estimates of sucessive failure and recovery times of a system. The mathematical model of system reliability is described by a dynamic automaton using the mathematical apparatus of many-valued and infinite-valued logic.Translated from Kibernetika, No. 5, pp. 104–111, September–October, 1990.     

Weak equivalence of automata

A generalization of Moore's theorem of weak equivalence of automata is derived. The weak equivalence problem and the existence problems of homing and diagnosing input-output sequences in an automaton are shown to be polynomially complete.Translated from Kibernetika, No. 5, pp. 85–89, September–October, 1990.     

Distance automata having large finite distance or finite ambiguity

A distance automaton is a (nondeterministic finite) automaton which is equipped with a nonnegative cost function on its transitions. The distance of a word recognized by such a machine quantifies the expenses associated with the recognition of this word. The distance of a distance automaton is the maximal distance of a word recognized by this machine or is infinite, depending on whether or not a maximum exists. We present distance automata havingn states and distance 2 ⁿ – 2. As a by-product we obtain regular languages having exponential finite order. Given a finitely ambiguous distance automaton withn states, we show that either its distance is at most 3 ⁿ – 1, or the growth of the distance in this machine is linear in the input length. The infinite distance problem for these distance automata is NP-hard and solvable in polynomial space. The infinite-order problem for regular languages is PSPACE-complete.A preliminary version of this article appeared in theProceedings of the 15th Symposium on Mathematical Foundations of Computer Science, 1990.     

Application of growing probabilistic automata for mathematical modeling

We define a growing probabilistic automaton and show how it can be used to predict the behavior of some process from its initial segment.Translated from Kibernetika, No. 1, pp. 88–90, January–February, 1989.     

Principles of logic optimization for a moore microprogrammed automaton

Conclusions  The existence of pseudoequivalent states permits minimizing the length of the direct structural table of the Moore automaton and thus reduces the number of terms in the system of automaton memory excitation functions. Automaton logic optimization requires unique identification of the classes of pseudoequivalent states. Method M₁ identifies the classesB _i ∈ π_ga without using additional variables and states. However, the application of this method does not always reduce the DST to the corresponding parameter of the equivalent Mealy automaton. Moreover, forR > R ₀ the number of feedback parameters in the Moore automaton is greater than in the equivalent Mealy automaton. Method M₂ attains the absolute minimum DST length and the absolute minimum number of feedback variables, which are equal to the corresponding parameters of the equivalent Mealy automaton. Moreover, state encoding can be applied that minimizes the number of terms in the microoperation system. However, M₂ requires the introduction of a special code converter and thus involves additional hardware costs. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 65–72, January–February, 1998.     

Automaton models of swapping and replacement systems for computer memory

We investigate various swapping and replacement systems for computer memory using infinite deterministic and nondeterministic automaton models. Some propositions are proved which lead to exact or approximate determination of the set of reachable memory states.Translated from Kibernetika, No. 4, pp. 9–18, 51, July–August, 1989.     

Vectorial languages and linear temporal logic

Determining for a given deterministic complete automaton the sequence of visited states while reading a given word is the core of important problems with automata-based solutions, such as approximate string matching. The main difficulty is to do this computation efficiently. Considering words as vectors and working on them using vectorial operations allows to solve the problem faster than using local operations.

In this paper, we show first that the set of vectorial operations needed by an algorithm representing a given automaton depends on the language accepted by the automaton. We give precise characterizations for star-free, solvable and regular languages using vectorial algorithms. We also study classes of languages associated with restricted sets of vectorial operations and relate them with languages defined by fragments of linear temporal logic.

Finally, we consider the converse problem of constructing an automaton from a given vectorial algorithm. As a byproduct, we show that the satisfiability problem for some extensions of LTL characterizing solvable and regular languages is PSPACE-complete.     

Reliable synthesis of logic circuits

The paper considers the construction of arbitrarily reliable logic circuits from unreliable components under more general fault assumptions than those of von Neumann and subsequent authors.Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 167–172, May–June, 1992.     

Modal extension of logic programming systems

Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 180–182, November–December, 1993.     

Tunable multifunction logic modules based on parametric representation of functions of k-valued logic over quasifields

We propose a new class of tunable logic modules that realize functions of k-valued logic. These modules are characterized by homogeneous structure and linear dependence of the number of tunable inputs on the number of input variables.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 24–29, July–August, 1991.