Decidability of the problem of semantic equivalence of words in the class of syntax-directed translations

Translated from Kibernetika, No. 5, pp. 38–41, September–October, 1988.     

词义刻画与词义识别

为了改善词义识别的效果,使词义识别技术水平获得实质性的提高,需要考察词义刻画与词义理解之间的关系,确定是否有必要重新刻画词语的词义,需要从理论和实验角度进行探讨。从语言学角度分析了影响词义刻画的各种因素,并设计和实现了人机词义识别的对比实验,借以揭示词义刻画粒度大小与词义识别精度之间的关系,进而说明调整词义刻画粒度的必要性。实验结果表明,科学控制词义刻画的粒度可以增强词义的可计算性,提高词义识别的精度。     

Application of semantic features in face recognition

We propose a new face recognition strategy, which integrates the extraction of semantic features from faces with tensor subspace analysis. The semantic features consist of the eyes and mouth, plus the region outlined by the centers of the three components. A new objective function is generated to fuse the semantic and tensor models for finding similarity between a face and its counterpart in the database. Furthermore, singular value decomposition is used to solve the eigenvector problem in the tensor subspace analysis and to project the geometrical properties to the face manifold. Experimental results demonstrate that the proposed semantic feature-based face recognition algorithm has favorable performance with more accurate convergence and less computational efforts.     

Analysis of semantic relations in classification of sense images of statements

Semantic relations in classification of images of natural-language statements are analyzed. The classification of the sense images of statements is considered on an example of construction of semantic relations in the RussNet thesaurus. The semantic statements are formalized with mathematical methods of the lattice theory. Gennadii M. Emel’yanov. Born 1943. Graduated from Leningrad Institute of Electrical Engineering in 1966. Received candidate’s degree in 1971 and doctoral degree in 1990. Head of the Department of Computer Software for Computer Devices and Computerized Systems at Novgorod State University. Scientific interests: construction of problem-oriented computer systems for image processing and analysis. Dmitrii V. Mikhailov. Born 1974. Graduated from Novgorod State University in 1997. Received candidate’s degree in 2003. Staff member of the Department of Computer Software for Computer Devices and Computerized Systems at Novgorod State Unniversity. Member of the Russian Association of Pattern Recognition and Image Analysis since 2002. Scientific interests: computer linguistics and artificial intelligence. Author of 15 papers. Nadezhda A. Stepanova. Born 1979. Graduated from Novgorod State University in 2001. PhD Student at Novgorod State University. Scientific interests: computer linguistics, semantics, lattice theory, intensional logic.     

Filling in the government-pattern dictionary in the analysis of equivalence for sense images of statements

Automatic filling in a language knowledgebase in analysis of the sense equivalence of statements is considered in the framework of an original approach based on a theory that represents language as a sense-to-text converter. Gennadii M. Emel’yanov. Born 1943. Graduated from Leningrad Institute of Electrical Engineering in 1966. Received candidate’s degree in 1971 and doctoral degree in 1990. Head of the Department of Computer Software for Computer Devices and Computerized Systems at Novgorod State University. Scientific interests: construction of problem-oriented computer systems for image processing and analysis. Dmitrii V. Mikhailov. Born 1974. Graduated from Novgorod State University in 1997. Received candidate’s degree in 2003. Staff member of the Department of Computer Software for Computer Devices and Computerized Systems at Novgorod State Unniversity. Member of the Russian Association of Pattern Recognition and Image Analysis since 2002. Scientific interests: computer linguistics and artificial intelligence. Author of 15 papers.     

The equivalence problem of multidimensional multitape automata

This article considers the equivalence problem of multitape automata with multidimensional tapes, where the motion of the heads is monotone in all directions (no backward motion). It is shown that this problem can be reduced to the equivalence problem of ordinary multitape automata. Some applications of the result are adduced.     

A semantic equivalence for Bio-PEPA based on discretisation of continuous values

Bio-PEPA is a process algebra for modelling biological systems. An important aspect of Bio-PEPA is the ability it provides to discretise concentrations resulting in a smaller, more manageable state space. The discretisation is based on a step size which determines the size of each discrete level and also the number of levels. This paper considers the relationship between two discretisations of the same Bio-PEPA model that differ only in the step size and hence the number of levels, by using the idea of equivalence from concurrency and process algebra. We present a novel behavioural semantic equivalence, compression bisimilarity, and investigate when this equates two discretisations of the same model and the circumstances in which this equivalence is a congruence with respect to the synchronisation operator.     

Decidability of the equivalence problem for deterministic pushdown automata

Decidability of the equivalence problem is proved for deterministic pushdown automata. A comparison algorithm for two automata is described. The main theorem leads to solution of a number of open problems in the theory of program schemes and in formal language theory.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 20–45, September–October, 1992.     

On the decidability of the sequence equivalence problem for DOL-systems

A property, called smoothness, of a family of DOL-systems is introduced. It is shown that the sequence equivalence problem is decidable for every smooth family of DOL-systems.Then a large subfamily of DOL-systems, called simple DOL-systems is shown to be smooth.     

On the equivalence of data base schemas—a semantic approach to data translation

A notion of the equivalence of data is the basis for deriving a correct translation of data bases. The equivalence of data base states and data base schemas is defined. Since this definition can only be given with respect to the semantics of data, a short discussion of data base semantics is given. It is shown, how a semantic data model and data definition language (LDDL) can be used to construct a correct specification of a translation function. Finally, an example of the translation of a CODASYL data base schema to a relational data base schema is given.     

Syntactic/semantic techniques in pattern recognition: A survey

This paper surveys some of the contemporary work in syntactic/semantic pattern recognition, with emphasis on four topics that are active research areas. These areas-grammatical inferrence, probabilistic models, syntactic errorcorrection, and grammars with attributes-present challenging questions both as to theory and as to practice.Portions of the paper are adapted from Syntactic Methods in Pattern Recognition, M. G. Thomason, to appear in theProceedings of the NATO Advanced Study Institute, Oxford University, 1981 J. Kittler, Ed. (D. Reidel Publishing Company. Dordrecht, Holland).     

A new bound for the D0L sequence equivalence problem

The D0L sequence equivalence problem consists of deciding, given two morphisms , and a word , whether or not g ⁱ (w) = h ⁱ (w) for all i ≥ 0. We show that in case of smooth and loop-free morphisms, to decide the D0L sequence equivalence problem, it suffices to consider the terms of the sequences with , where n is the cardinality of X.