Finite transducers, two-tape automata, and biautomata are related computational models descended from the concept of Finite-State Automaton. In these models an automaton controls two heads that read or write symbols on the tapes in the one-way mode. The computations of these three types of automata show many common features, and it is surprising that the methods for analyzing the behavior of automata developed for one of these models do not find suitable utilization in other models. The goal of this paper is to develop a uniform technique for building polynomial-time equivalence checking algorithms for some classes of automata (finite transducers, two-tape automata, biautomata, single-state pushdown automata) which exhibit certain features of the deterministic or unambiguous behavior. This new technique reduces the equivalence checking of automata to solvability checking of certain systems of equations over the semirings of languages or transductions. It turns out that such a checking can be performed by the variable elimination technique which relies on some combinatorial and algebraic properties of prefix-free regular languages. The main results obtained in this paper are as follows:

1.            Using the algebraic approach a new algorithm for checking the equivalence of states of deterministic finite automata is constructed; time complexity of this algorithm is O(n log n).

2.            A new class of prefix-free finite transducers is distinguished and it is shown that the developed algebraic approach provides the equivalence checking of transducers from this class in quadratic time (for real-time prefix-free transducers) and cubic (for prefix-free transducers with ɛ-transitions) relative to the sizes of analysed machines.

3.            It is shown that the equivalence problem for deterministic two-tape finite automata can be reduced to the same problem for prefix-free finite transducers and solved in cubic time relative to the size of the analysed machines.

4.            In the same way it is proved that the equivalence problem for deterministic finite biautomata can be solved in cubic time relative to the sizes of analysed machines.

5.            By means of the developed approach an efficient equivalence checking algorithm for the class of simple grammars corresponding to deterministic single-state pushdown automata is constructed.

Raphael Robinson showed that all primitive recursive functions depending on one argument, and only they could be obtained from two functions s(x) = x +1 and q(x) = x - [√x]² by using operations of addition +, superposition ∗ and iteration i. Julia Robinson proved that from the same two functions, using the addition +, superposition ∗ and operation ¯¹ of function inversion, one could obtain all general recursive functions (under a certain condition on the inversion operation) and all partially recursive functions. On the basis of these results, A. I. Maltsev brought into consideration the Raphael Robinson algebra of all unary primitive recursive functions and two Julia Robinson algebras: the partial algebra of all unary general recursive functions and the algebra of all unary partially recursive functions and proposed to study the properties of these algebras, including the question of the existence of finite bases of identities in these algebras. In this article we show that there is no finite basis of identities in any of the indicated algebras.

To ensure traffic safety of railway transport, non-destructive test of rails is regularly carried out by using various approaches and methods, including eddy-current flaw detection methods. An automatic analysis of large data sets (defectograms) that come from the corresponding equipment is an actual problem. The analysis means a process of determining the presence of defective sections along with identifying structural elements of railway tracks in defectograms. This article is devoted to the problem of recognizing images of long structural elements of rails in eddy-current defectograms. Two classes of rail track structural elements are considered: 1) rolling stock axle counters, 2) rail crossings. Long marks that cannot be assigned to these two classes are conditionally considered as defects and are placed in a separate third class. For image recognition of structural elements in defectograms a convolutional neural network is applied. The neural network is implemented by using the open library TensorFlow. To this purpose each selected (picked out) area of a defectogram is converted into a graphic image in a grayscale with size of 30 x 140 points.

The article is devoted to comparison of stylometric features of several levels, which are markers of the style of the prose text and analysis of the stylistic changes in Russian and British prose of the 19th-21st centuries. Stylometric features include the low-level features based on the words and symbols and high-level based on rhythmic. These features model the style of a text and are the indicators of the time when the text was created.

Calculations of all the features are performed completely automatically, so it allows to conduct the large-scale experiments with artworks of a large volume and speeds up the work of a linguist. To calculate the stylometric features including ones based on the search results for rhythmic figures the ProseRhythmDetector program is used. As a result of its work, each text is presented as a set of the same features of three levels: characters, words, rhythm. Texts are combined by decades, for each decade there are found average values of stylometric features. The obtained models of decades are compared using standard similarity metrics, results of comparison are visualized in the form of the heat maps and dendrograms. Experiments with two corpora of Russian and British texts show that during the 19th-21st centuries there are general trends in style change for both corpora, for example, a decrease in the number of rhythmic figures per sentence, and also particular trends for each language, for example, dynamics of change of the word and sentence lengths. Stylometric features of all levels reveal the similarity in the style of texts published in one century. Also, features of three levels in the complex better demonstrate the uniqueness of each decade than features of a particular level. This study shows the importance of stylometric features as style markers of the different eras and allows us to identify trends in style during several centuries.

The logistic equation with delay or Hutchinson’s equation is one of the fundamental equations of population dynamics and is widely used in problems of mathematical ecology. We consider a family of mappings built for this equation based on central separated differences. Such difference schemes are usually used in the numerical simulation of this problem. The presented mappings themselves can serve as models of population dynamics; therefore, their study is of considerable interest. We compare the properties of the trajectories of these mappings and the original equation with delay. It is shown that the behavior of the solutions of the mappings constructed on the basis of the central separated differences does not preserve, even with a sufficiently small value of the time step, the basic dynamic properties of the logistic equation with delay. In particular, this map does not have a stable invariant curve bifurcating under the oscillatory loss of stability of a nonzero equilibrium state. This curve corresponds in such mappings to the stable limit cycle of the original continuous equation. Thus, it is shown that such a difference scheme cannot be used for numerical modeling of the logistic equation with delay.

In this paper a generalisation of the inference rules of the join dependencies that are used in the design of database schemas that meets the requirements of the fifth normal form is considered. In the previous works devoted to this problem, attempts to construct systems of the axioms of such dependencies based on inference rules are made. However, while the justification for the consistency (soundness) of the obtained axioms does not cause difficulties, the proof of completeness in general has not been satisfactorily resolved. First of all, this is due to the limitations of the inference rules themselves. This work focuses on two original axiom systems presented in the works of Sciore and Malvestuto. For the inclusion dependencies a system of rules that generalises existing systems and has fewer restrictions has been obtained. The paper presents a proof of the derivability of known systems of axioms from the presented inference rules. In addition, evidence of the consistency (soundness) of these rules is provided. The question of the completeness of the formal system based on the presented rules did not find a positive solution. In conclusion, the theoretical and practical significance of the inference rules for the join dependencies is noted.