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.     

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.     

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.     

关系代数派生算子语义表达式间等价性证明

关系代数的派生算子在关系数据库查询语言中得到了广泛应用。它们的语义有两种常见的表示方式,一种是基于原始算子的表达式,一种是基于一阶逻辑的表达式。但有关的文献资料都没有给出这两种表达式等价性的严格证明。文章尝试通过一系列等价变换,证明派生算子语义的这两种表达式间的等价性。从派生算子(主要是除算子)语义的原始算子表达式出发,根据关系代数表达式的特点,通过一步步的等价变换,得到派生算子语义的一阶逻辑表达式。所使用的变换方法能为关系代数表达式的正确性证明打下基础。     

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.     

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.     

认知学习中的知识约等价问题

人类的知识获取过程通常是利用已有知识来推知相关知识的过程,机器学习可以借助这一过程,从学习的逆过程出发,把知识作为学习的出发点,来对认知学习进行研究和应用。以已有的知识作为参照知识,经过等价变换或约等价变换,产生新的知识。约等价变换过程包括知识的约等价扩充和约等价约简。等价变换过程处理同一层次的知识,约等价扩充过程产生细节级知识,约等价约简过程产生抽象级知识。实例分析表明,采用知识的约等价扩充和约简算法所产生的新知识的准确率较高,能够产生当前已有知识的细节级和抽象级新知识,为认知机器学习的知识处理提供了一定参考。     

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.     

潜在语义分析在连续语音识别中的应用

研究了潜在语义分析（LSA）理论及其在连续语音识别中应用的相关技术,在此基础上利用WSJ0文本语料库上构建LSA模型,并将其与3-gram模型进行插值组合,构建了包含语义信息的统计语言模型;同时为了进一步优化混合模型的性能,提出了基于密度函数初始化质心的k-means聚类算法对LSA模型的向量空间进行聚类。WSJ0语料库上的连续语音识别实验结果表明：LSA+3-gram混合模型能够使识别的词错误率相比较于标准的3-gram下降13.3%。     

The associativity of equivalence and the Towers of Hanoi problem

Dijkstra and Scholten have argued that greater use should be made of the associativity of equivalence. This note shows how the property is used in specifying the rotation of the disks in the well-known Towers of Hanoi problem.     

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.