[Bruijn, 1946] N. G. de Bruijn. A combinatorial problem. In Koninklijke Nederlandsche Akademie van Wetenschappen, volume 49, 1946.
[Cormode, 2000] G. Cormode, M. Paterson, S. C. Sahinalp, U. Vishkin. Communication complexity of text exchange. In Proc.
of the 11th ACM-SIAM Annual Symposium on Discrete Algorithms, pp. 197--206, San Francisco, CA, [Datar, 2004] M. Datar, N. Immorlica, P. Indyk, V. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In 20-th annual symposium on Computational geometry, pages 253–262, Brooklyn, New York, USA, 2004.
[Indyk, 1998] P. Indyk, R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proc.
of 30th STOC, pages 604–613, 1998.
[Indyk, 2001] P. Indyk. Algorithmic aspects of geometric embeddings. In FOCS, 2001.
[Indyk, 2004] P. Indyk. Embedded stringology. Talk at 15-th Annual Combinatorial Pattern Matching Symposium, July 2004.
[Kussul, 1991] Kussul, E. M., & Rachkovskij, D. A. (1991). Multilevel assembly neural architecture and processing of sequences. In A. V. Holden & V. I. Kryukov (Eds.), Neurocomputers and Attention: Vol. II. Connectionism and neurocomputers (pp. 577-590). Manchester and New York: Manchester University Press.
[Levenshtein, 1966] V. I. Levenshtein. Binary codes capable of correcting deletions,insertions, and reversals. Soviet Physics - Doklady, 10(8):707–710, February 1966.
[Matouek, 2002] Open problems. In J. Matouek, editor, Workshop on Discrete Metric Spaces and their Algorithmic Applications, Haifa, March 2002.
[Navarro, 2001] G. Navarro. A guided tour to approximate string matching. ACM Computing Surveys, 33(1):31–88, 2001.
[Pevzner, 1989] P. A. Pevzner,P. L-tuple DNA sequencing: computer analysis. J. Biomol. Struct. Dyn., 7, 63–73,[Pevzner, 1995] P. A. Pevzner. Dna physical mapping and alternating eulerian cycles in colored graphs. Algorithmica, 13(1/2):77–105, 1995.
[Rachkovskij, 2001] D. A. Rachkovskij, E. M. Kussul. Binding and Normalization of Binary Sparse Distributed Representations by Context-Dependent Thinning, Neural Comp. 13: 411-452, 2001.
[Shamir, 2004] R. Shamir. Lecture notes in Analysis of Gene Expression Data, DNA chips and Gene Networks: Sequencing by hybridization. www.cs.tau.ac.il/~rshamir/ge/04/scribes/lec02.pdf, 2004.
[Sokolov, 2005] A. Sokolov, D. Rachkovskij. Some approaches to distributed encoding of sequences. In Proc. of XI-th International Conference Knowledge-Dialogue-Solution, volume 2, pages 522–528, Varna, Bulgaria, June 2005.
[Ukkonen, 1992] E. Ukkonen. Approximate string-matching with q-grams and maximal matches. Theor. Comput. Sci., 92(1):191–211, 1992.
[Vintsyuk, 1968] T. K. Vintsyuk. Speech discrimination by dynamic programming. Kibernetika (Cybernetics), (4):81–88, 1968.
[Wagner, 1974] R. A. Wagner, M. J. Fischer. The string-to-string correction problem. Journal of the ACM, 21(1):158–173, January 1974.
Authors' Information Artem M. Sokolov – International Research and Training Center of Information Technologies and Systems;
Pr. Acad. Glushkova, 40, Kyiv, 03680, Ukraine; e-mail: sokolov (at) ukr.net Ontologies DOMAIN ONTOLOGIES AND THEIR MATHEMATICAL MODELSAlexander S. Kleshchev, Irene L. Artemjeva Abstract: In this article the notion of a mathematical model of domain ontology is introduced. The mathematical apparatus (unenriched logical relationship systems) is essentially used. The representation of various elements of domain ontology in its model is considered. These elements are terms for situation description and situations themselves, knowledge and terms for knowledge description, mathematical terms and constructions, auxiliary terms and ontological agreements. The notion of a domain model is discussed. The notions of a precise ontology and precise conceptualization are introduced. The structures of situations and knowledge and also their properties are considered. Merits and demerits of various classes of the domain ontology models are discussed.
Keywords: Domain ontology, domain ontology model, ontology language specification, kernel of extendable language of applied logic, unenriched logical relationship systems, enriched logical relationship systems, enrichment of logical relationship system.
ACM Classification Keywords: I.2.4 Knowledge Representation Formalisms and Methods, F4.1. Mathematical Logic Introduction A few different definitions for the notion of domain ontology have been suggested by now. But every definition has certain flaws. Because different interpretations of the notion of a domain ontology are used when different problems related to domain ontologies are solved, it may be deduced that now there is no universally accepted definition of the notion. This article suggests another definition of the notion of domain ontology. As this takes place, the mathematical apparatus (unenriched logical relationship systems) introduced in [1-3] is essentially used.
A Mathematical Model of a Domain Ontology An unenriched logical relationship system  can be considered as a domain ontology model, if each of its logical relationship has a meaningful interpretation that a community of the domain agrees with, and the whole system is an explicit representation of a conceptualization of the domain understood both as a set of intended situations and as a set of intended knowledge systems of the domain. Some examples of unenriched logical relationship systems and their meaningful interpretations as models of simplified domain ontologies were given in [1-2].
Models of ontologies for medicine close to real notions of the domain were described in . Models of ontologies for physical and organic chemistry and also for roentgen fluorescent analysis were described in [6-9]. Model of ontology for classical optimizing transformations is described in [10-12].
Information concerning a finite (real or imaginary) fragment of a real or imaginary reality (the fragment may be related to a finite part of the space and to a finite time lapse) will be called a situation (a state of affairs in terms of ), if this fragment contains a finite set of objects and a finite set of relations among them.
Objects and relations (including unary ones) among them depending on situations are designated by special domain terms which will be called terms for situation description. Objects in situation models can be represented:
This paper was made according to the program № 14 of fundamental scientific research of the Presidium of the Russian Academy of Sciences, the project "Intellectual systems based on multilevel domain models".
Ontologies by elementary mathematical objects (numbers and so on); by names having neither sort nor value  (such a name is a designation of an object); by structural mathematical objects (sets, n-tuples, and so on) constructed of elementary or structural mathematical objects or names having neither sort nor value by composition rules defined in the language of applied logic.
The set of names having neither sort nor value and used as designations of objects (and their components) in situation models can be determined explicitly or implicitly in a domain ontology model. In the former case, all these names appear in sort descriptions for unknowns. In the latter case, all these names are constituents of parameter values. In the domain ontology model the names of these parameters are used for describing sorts of unknowns. If a domain ontology model determines some names having neither sort nor value then these names have the same meaning in every situation of the domain. A domain ontology model can determine only some of the names having neither sort nor value and used in situations for designating objects (and their components). In this case these names are determined by a model of situation and may have different meaning in different situations.
Unknowns represent relations among objects depending on situations. In different situations the relations corresponding to the same unknown can be different. Every objective unknown designates a role that in each situation an (unique) object of the situation plays, and also in every situation there is its own object playing the role. Every functional unknown designates a set of functional relations. For each situation this functional relation is the one among objects of the situation. For different situations these relations corresponding to the same unknown can be different. Analogously, every predicative unknown designates a set of nonfunctional relations.
For each situation this nonfunctional relation (it may be empty) is the one among objects of the situation. For different situations these relations corresponding to the same unknown can be different.
Thus, every unknown can be considered as a designation of a one-to-one correspondence between situations and the values of the unknown in these situations.
The sort description for an unknown determines the set of value models for the unknown. In any (real or imaginary) situation only an element of this set can be a value of the unknown. Thereby, the sort description for an unknown determines a model of the capacity for the concept designated by the unknown. A model of the capacity for a concept can be both a finite and infinite set.
A model of a (real or imaginary) situation is a set of values of the unknowns for the unenriched logical relationship system representing a domain ontology model. A model of a situation can be represented by a set of value descriptions for the unknowns.
Knowledge Models and Terms for Knowledge Description If an unenriched logical relationship system is a model of a domain ontology then any of its enrichments is a model of a knowledge system for the domain. If a model of a domain ontology is an unenriched logical relationship system O without parameters, then the ontology model introduces all the terms for description of the domain. In this case any enrichment k of the system O is a set of logical relationships – restrictions on the interpretation of names representing empirical or other laws of the domain. Since this enrichment does not introduce any new names it cannot contain any sort descriptions for names .
If a model of a domain ontology is an unenriched logical relationship system with parameters, then the parameters of the system are the domain terms which are used for knowledge description.
If a model of domain ontology is a pure unenriched logical relationship system O with parameters then any enrichment k of the system O is a set P of the parameter values for the system O . A value of an objective parameter determines a feature of the domain, a set of names for situation description, or a set of parameter names. Every enrichment (a knowledge base) can introduce new names as compared with the ontology – terms for situation and knowledge description. Functional and predicative parameters represent empirical or other laws of the domain. The value of every functional or predicative parameter is some relation among terms and/or domain constants. In this case domain knowledge is described at a higher level of abstraction than in the case when a domain ontology model is an unenriched logical relationship system without parameters. The values of parameters can be represented by a set of propositions – value descriptions for names.
If a model of a domain ontology is a mixed unenriched logical relationship system O with parameters, then any enrichment k of the system O is a pair <', P>, where ' is a set of logical relationships (restrictions on the interpretation of names) representing a part of empirical or other domain laws, and P is a set of parameter XII-th International Conference "Knowledge - Dialogue - Solution" values for the system O representing the other domain laws . In this case domain knowledge is represented at two levels of abstraction: as logical relationships among unknowns of the system O and as relations among terms of the domain (as parameter values of the system O).
The sort description for a parameter determines the set of value models for the parameter. In any knowledge model only an element of this set can be a value of the parameter. Thereby, the sort description for a parameter determines a model of the capacity for the concept designated by the parameter. A model of the capacity for a concept can be both a finite and infinite set.
Mathematical Terms and Constructions. Auxiliary Terms The language of applied logic  determines mathematical terms and constructions used for domain description in that the unenriched logical relationship system which is an ontology model for the domain is represented. The kernel of the applied logic language  determines a minimal set of logical means for domain description. The standard extension of the language  apart from additional logical means introduces arithmetic and set-theoretic constants, operations and relations. Every specialized extension  of the language gives us a possibility to define both additional logical means and constants, operations and relations of other divisions of mathematics.
The specialized extensions Intervals and Mathematical quantors of language  introduce integer-valued and real-valued intervals, and also mathematical quantifiers. Other examples of mathematical terms which can be introduced by specialized extensions are operations of differentiation and integration, predicates of optimization, and the like.
Mathematical objects (names, numbers, sets, n-tuples, and the like) serve to represent models of elementary and combined domain objects. Mathematical functions and relations represent the properties of domain objects which are kept with mathematical models in place of domain objects. In every domain a specific mathematical apparatus is used, as a rule. This property of domains is represented by specialized extensions of the language in domain ontology models. At the same time, the practice shows that the same mathematical apparatus can be used for description of different domains. In this case, for description of ontology models of these domains the same specialized extensions of the applied logic language given by the names of these extensions can be used.
Thus, mathematical terms and constructions have more or less universally accepted designations, syntax and semantics. They are separated from a domain ontology by their definition in the applied logic language (in its kernel and extensions) rather than in the unenriched logical relationship system representing the ontology model.
Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.