Attestation committee
Accreditation committee
Expert committee
Dispositions, instructions
Normative acts
MANPOWER TRAINING
Nomenclature
Institutions
Scientific councils
Seminars
Theses		 Scientific advisers
Scientists
Doctoral students
Postdoctoral students
CNAA logo

 română | русский | english

CNAA / Theses / 2019 / May /

Distances on Free Monoids and Their Applications in Theory of Information


Author: Budanaev Ivan
Degree:doctor of physics and mathematics
Speciality: 01.01.06 - Mathematical logics, algebra and theory of numbers
Year:2019
Scientific adviser: Mitrofan Cioban
doctor habilitat, professor
Institution:

Status

The thesis was presented on the 14 May, 2019
Approved by NCAA on the 6 December, 2019

Abstract

Adobe PDF document – 0.30 Mb / in romanian
Adobe PDF document – 0.30 Mb / in english

Thesis

CZU 512.536.7+515.122.4,004.424.62

Adobe PDF document 0.77 Mb / in english
135 pages

Keywords

Alexandroff space, quasivariety of topological monoids, free monoids, invariant distance, quasi-metric, Levenshtein distance, Hamming distance, Graev distance, parallel decomposition, proper similarity, weighted mean, bisector of two strings, convexity, algorithm

Summary

Thesis structure: the thesis is written in English and consists of: introduction, four chapters, general conclusions and recommendations, 200 bibliography titles, 116 pages of main text. The obtained results were published in 20 scientific papers.

Domain of research: Distances on abstract algebraic structures.

Goals and objectives: The goal of the research is to study the problem of distances on free monoids. To achieve this goal, the following objectives were defined: elaboration of an effective method for extending the quasi-metric on free monoids; development of efgicient representations of information for data analysis; implementation of innovative algorithms for solving text sequences problems; describe digital topologies on the discrete line.

The scientific novelty and originality consist in obtaining new theoretical results with applications in computer science. An effective method of distance extension on free monoids was developed, which helped to introduce the concept of parallel representation of information. This has allowed the development of the concepts of efficiency and similarity of the information sequences, as well as the construction of the sets of weighted mean and bisector of strings.

The important scientific problem solved in the research is the development of methods for constructing and studying distances on free monoids, which contribute to obtaining effective methods of representing information, applicable to solving different distance problems.

The theoretical significance is determined by the obtaining of the new results regarding the establishment of the conditions of existence of the extension of the distance on free monoids. The elaborated methods have allowed to approach the problems related to information sequences from a new point of view. New algorithms of constructing strings weighted mean and bisector were proposed. It has been established that the informational segment is not convex.

The applicative value of the paper consists in the use of the obtained theoretical results in the study of symmetric topologies on the digital line, imaging processing and construction of the centroid of a set of strings.

The implementation of the scientific results. The obtained results can be used in scientific research related to data analysis, the study of the efficiency of information representation, digital image processing. They can also be used in development of an optional course for university students related to the study of distances on abstract algebraic structures.

Summary


1 CURRENT SITUATION IN THE FIELD OF QUASI-METRIC SPACE THEORY AND THEIR APPLICATIONS IN ALGEBRA AND INFORMATION THEORY
  • 1.1 Distance spaces
  • 1.2 On discrete spaces
  • 1.3 Abstract information systems
  • 1.4 Universal topological algebras
  • 1.5 Spaces of strings. Languages
  • 1.6 Free algebras. Maltsev’s Problems
  • 1.7 Conclusions for chapter 1

2 EXTENSION OF QUASI-METRICS ON FREE TOPOLOGICAL MONOIDS
  • 2.1 Free topological monoids
  • 2.2 Construction of the abstract free monoid
  • 2.3 On the non-Burnside quasivarieties
  • 2.4 Extension of pseudo-quasi-metrics
  • 2.5 Strongly invariant quasi-metrics
  • 2.6 Free monoids of T0 -spaces
  • 2.7 Free semi-topological monoids of T0 -spaces
  • 2.8 On topological digital spaces
  • 2.9 Conclusions for chapter 2

3 MEASURES OF SIMILARITY ON MONOIDS OF STRINGS
  • 3.1 Monoid of strings on alphabet A
  • 3.2 Relations to Hamming and Levenshtein distances
  • 3.3 Efficiency and penalty of two strings
  • 3.4 Computational algorithms of distances
  • 3.5 General applications and examples
  • 3.6 Conclusions for chapter 3

4 GEOMETRICAL AND TOPOLOGICAL ASPECTS OF INFORMATION ANALYSIS
  • 4.1 Construction of the weighted means of a pair of strings
  • 4.2 Problem of convexity of the set of weighted means
  • 4.3 Construction of the bisector of a pair of strings
  • 4.4 Alexandroff spaces
  • 4.5 Scattered and digital topologies in image processing
  • 4.6 Algorithms and scattered spaces
  • 4.7 Local finiteness and digital spaces
  • 4.8 Discrete line and scattered spaces
  • 4.9 Conclusions for chapter 4

GENERAL CONCLUSIONS AND RECOMMENDATIONS
REFERENCES
DECLARATION OF LIABILITY
CURRICULUM VITAE