不确定系统中的伪加权下推计算模型研究

Pushdown computational models based on semirings are not only important mathematical models in theoretical computer science but also one class of the most extensive pushdown computational models in uncertain systems at present, which have been widely used for the fields such as natural languages processing, algorithm design and artificial intelligence. This proposal will generalize the codomains of pushdown computational models to pseudo semirings, investigate pseudo weighted pushdown computational models in uncertain systems from two aspects of computing power and algebraic properties, namely pseudo weighted pushdown automata and pseudo weighted context-free grammars. Firstly, based on breadth-first semantics, the run semantics and the initial algebraic semantics, the relationships among the different types of pseudo weighted pushdown automata will be discussed, and then the properties of pseudo weighted pushdown automata will be investigated. Secondly, simple types of pseudo weighted context-free grammars will be given, which should be equivalent to pseudo weighted pushdown automata. By introducing algebraic systems of pseudo semirings, the interconnections between pseudo weighted context-free grammars and algebraic systems of pseudo semirings will be discussed, and moreover the solution structure and its existent condition for the algebraic systems of pseudo semirings will be explored. Finally, this proposal will study the application of pseudo weighted pushdown computational models in supervisory control and safety diagnosis of uncertain discrete event systems. The study will be helpful for the development and perfection of computational models theory in uncertain systems. It also will provide meaningful guidance for selecting various computing models reasonably in practical application.

基于半环的下推计算模型不仅是理论计算机科学中的重要数学模型, 还是目前不确定系统中研究最广泛的下推计算模型之一，已被广泛应用于自然语言的处理、算法设计和人工智能等领域。本项目拟将下推计算模型的取值论域推广到伪半环上, 从计算能力、代数性质两方面研究不确定系统中的伪加权下推计算模型，即伪加权下推自动机及伪加权上下文无关文法。基于宽度优先语义、运行语义与初始代数语义，拟首先研究不同类型伪加权下推自动机之间的关系及其性质; 其次,给出等价于伪加权下推自动机的形式简明型伪加权上下文无关文法，通过引入伪半环代数系统，建立伪加权上下文无关文法与伪半环代数系统之间的联系，探究伪半环代数系统的解结构及其解存在的条件；最后，研究伪加权下推计算模型在不确定离散事件系统中的监控、安全诊断方面的应用。该研究将有助于发展与完善不确定系统中的计算模型理论,且对实际应用中不同计算模型的合理选取具有重要的指导意义。

基于半环的下推计算模型不仅是理论计算机科学中的重要数学模型, 还是目前不确定系统中研究最广泛的下推计算模型之一，已被广泛应用于自然语言的处理、算法设计和人工智能等领域。本项目将下推计算模型的取值论域推广到伪半环上, 从计算能力、代数性质两方面研究不确定系统中的伪加权下推计算模型，即伪加权下推自动机及伪加权上下文无文法。基于宽度优先语义、运行语义与初始代数语义，首先研究不同类型伪权下推自动机之间的关系及其性质。其次,给出等价于伪加权下推自动机的形式简明型伪加权上下文无关文法，通过引入伪半环代数系统，建立伪加权上下文无关文法与伪半环代数系统之间的联系，探究伪半环代数系统的解结构及其解存在的条件。然后，研究带有单输入与多输出功能的赋值幺半群加权自动机，其取值论域是带有赋值函数的交换幺半群，特别地，若论域是柯西双单位赋值幺半群，则加权序列自动机与加权Moore自动机等价。再次，给出量子可逆模糊有穷自动机与量子可逆模糊正则文法之间的等价性结论，研究量子可逆模糊文法的代数性质刻画。最后，研究伪加权下推计算模型在不确定离散事件系统中的监控、安全诊断方面的应用，用区间数、区间值多模糊软集、区间型随机变量及模糊随机变量处理不确定数据，研究模糊计算模型在多目标优化控制决策及风险管理方面的应用。该研究将有助于发展与完善不确定系统中的计算模型理论,对实际应用中不同计算模型的合理选取具有重要的指导意义，还将推动计算模型在经济、军事、物流、金融和科学计算等应用领域不确定数据管理和优化方面的发展。