基于伪半环的不确定计算模型及其应用研究

Pseudo semirings can be viewed as semirings by dropping the distributivity. Uncertain computational models based on pseudo semirings is one class of the most extensive uncertain computational models at present, which have been widely applied in natural language processing, speech recognition, model checking, digital image compression and so on. This project mainly consider three kinds of uncertain computational models based on pseudo semirings, namely pseudo weighted finite automata, pseudo weighted transducers and pseudo weighted Turning machines，and their applications in new fields. Firstly, since the distributivity does not hold for pseudo semirings in general, four new semantics are put forward based on the existing three semantics, and the relationships among the different types of pseudo weighted finite automata under the seven different semantics are discussed, which are meaningful for selecting reasonable computational models in practice. Derived from the application of weighted automata in natural laguage processing, the conceptions of input-functions and output-functions of weighted transducers are given. And their realization will be considered. Secondly, the universality of the pseudo weighted Turning machines will be studied. The existence of universal pseudo weighted Turning machine is very important to the realization of pseudo weighted Turning machines. Finally, the applications of uncertain computational models based on pseudo semirings in uncertain information management will be studied, such as uncertain information expressing and uncertain data management.

伪半环是半环去掉分配律形成的代数结构。基于伪半环的不确定计算模型是目前最广泛的不确定计算模型之一，并被广泛应用于自然语言的处理、语音识别、模型检测及数字图像压缩等领域。本项目主要研究三种不确定计算模型，即伪加权有穷自动机、伪加权转换器、伪加权图灵机，及其在新的领域的应用。首先，由于伪半环中分配律一般不成立，提出了四种新的语义，结合已有的三种语义，在七种语义下讨论不同类型伪加权有穷自动机之间的关系，这对实际应用中计算模型的合理选取有很重要的意义；源于加权自动机在自然语言处理中的应用背景，提出伪加权转换器的输入函数与输出函数的概念，并考虑其实现化。其次，我们研究伪加权图灵机的通用性，伪加权通用图灵机是否存在对伪加权图灵机的实现是至关重要的。最后，研究基于伪半环的不确定计算模型在不确定性管理中的不确定信息的表达与不确定数据管理方面的应用。

伪半环，也称为强双半群，是半环去掉分配律形成的代数结构。一些重要的代数结构如半环、完备正交模格等都是伪半环的特例。而对于代数基础为半环的加权自动机、代数基础为格半群的格值模糊自动机以及代数基础为正交模格的基于量子逻辑的自动机的研究已有很多，并得到了很多重要的结论。从另外一个角度来看，伪半环也可以认为是半环和完备正交模格的共同推广。2010年，Droste等学者提出了基于伪半环的加权有穷自动机（伪加权有穷自动机）的概念，并做了一些初步研究。本项目就是在此基础上进一步研究伪加权自动机，包括伪加权有穷自动机，伪加权转换器，伪加权图灵机以及多维自动机的一些性质。在此基础上初步研究了伪加权自动机在不确定数据处理中的应用。. 首先，在不同语义下研究了不同类型的伪加权有穷自动机之间的关系，这对实际应用中不确定计算模型的合理选取有重要的意义；研究了伪加权转换器的性质，提出了输入函数和输出函数的概念，并给出了其实现化。其次，研究了伪加权图灵机及其变型的计算能力。但上述这些计算模型在不确定数据处理中有一定的局限，只能用来处理简单的二维不确定数据，为了处理多维不确定数据的问题，提出了多维自动机的概念，给出了投影函数的概念，研究了投影函数的实现化问题。实际上， 伪加权有穷自动机、伪加权转换器以及伪加权图灵机都是多维自动机的特例；进一步，研究了多维自动机在不确定数据处理中的初步应用，打开了自动机应用的一个新领域。最近的研究表明多维自动机和赋值代数之间有一定的联系，且二者在不确定信息的表达和提取均有很好的应用前景。本项目结题之后，将利用剩余经费继续研究多维自动机及赋值代数在信息的表达和数据处理中的应用。