Computer Sciences

On Recognition of Languages of Arbitrary words by Finite Semigroups

Based on methods of nonstandard analysis we elaborate in this paper a new approach to the theory of infinite products in finite semigroups. The main theorems of the paper show that infinite products of elements of standard sequences in finite semigroups can be viewed as a two-sided algebraic counterpart of finite products of a special kind. Using these results we construct a universal functor of the category of finite semigroups to the category of finite four-sorted algebras of a special kind and introduce a notion of a language of arbitrary words recognized by finite semigroups.

On Minimal Strongly Connected Congruences of a Directed Path

Let G = (V, α) be a directed graph. An equivalence relation θ ⊆ V × V is called a strongly connected congruence of G if the quotient graph  G/θ is strongly connected. Minimal (under inclusion) strongly connected congruences of a directed  path are described and the total amount of them is found.

Some Questions on Minimal Extensions of Graphs

Some statements concerning minimal extensions of graphs are presented that seem to be quite evident at first sight but are not so simple under closer inspection.

The Geometric Form of Automaton Mappings, Recurrent and Z-recurrent Definition of Sequences

For automaton mappings we present a method to construct geometric images, a method for complexity estimate by geometric forms, a method of Z-recurrent definition of sequences. A method for complexity estimate for finite sequences by recurrent and Z-recurrent numerical indicators is proposed. Numerical indicators of recurrent and Z-recurrent definitions of sequences are systematized into the spectrum of recurrent definitions with 5 levels of numerical indicators.

The Sperner Property for Polygonal Graphs Considered as Partially Ordered Sets

A finite poset is said to have the Sperner property if at least one of its maximum antichains is formed from elements of the same height. A polygonal graph is a directed acyclic graph derived from a circuit by some orientation of its edges. The reachability relation of a polygonal graph is a partial order. A criterion is presented for posets associated with polygonal graphs to have the Sperner property.



On Applications of Wavelets in Digital Signal Processing

Discrete Wavelet transform associated with the Walsh functions was defined by Lang in 1998. The article describes an application of Lang’s transform and some its modifications in analysis of financial time series and for the compression of fractal data. It is shown that for the processing of certain signals the studied discrete wavelet transform has advantages over the discrete transforms Haar, Daubechies and the method of zone coding.



Analyticity Conditions of Characteristic and Disturbing Quasipolynomials of Hybrid Dynamical Systems

Hybrid dynamical systems (HDS) are connected by means of the boundary conditions and the constraint’s conditions systems of ordinary differential equations and partial differential equations with the corresponding initial conditions. Check the stability of HDS can be performed on the basis of the "fast"algorithm for the application which requires analytic characteristic and disturbing quasipolynomials of HDS in the right half-plane and near the imaginary axis.

An Approach to Fuzzy Modeling of Digital Devices

In the article the problem of fuzzy binary logic modeling for digital devices (DD) is investigated. In contrast to the similar classic problem of logical simulation, it is assumed that inputs signals of DD are fuzzy signals. In the real of DD for each input (0 or 1) there is a certain voltage range. If an input signal is out of the range, the correct signal identification is not guaranteed. The fuzziness of input signals means that there observed values can be either within of the defined range, or out of it.

Quantum Computers and Quantum Algorithms. Part 2. Quantum Algorithms

The paper discusses principles of construction for quantum algorithms and their main features. Distinction of quantum parallelism from classical methods of high-performance computing is shown. Quantum algorithms design strategy is presented based on quantum circuits. Methods of programming for implementation of quantum algorithms using high-level languages are proposed. An approach to implement unitary transformations based on the oracle method is described.

Algebraic Properties of Abstract Neural Network

The modern level of neuroinformatics allows to use artificial neural networks for the solution of various applied problems. However many neural network methods put into practice have no strict formal mathematical substantiation, being heuristic algorithms. It imposes certain restrictions on development of neural network methods of the solution of problems. At the same time there is a wide class of mathematical models which are well studied within such disciplines as theory of abstract algebras, graph theory, automata theory.