Compiling CSPs into Tree-Driven Automata for Interactive Solving

Constraint programming techniques are widely used to model and solve decision problems and many algorithms have been developed to solve automatically and efficiently families of CSPs; nevertheless, they do not help solve interactive decision support problems, like product configuration. In such problems, the user chooses the values of the variables, and the role of the system is not to solve the CSP, but to help the user in this task. Dynamic global consistency maintaining is one of the most useful functionalities that should be offered by such a CSP platform. Unfortunately, this task is intractable in the worst case. Since interactivity requires short response times, intractability must be circumvented some way. To this end, compilation methods have been proposed that transform the original problem into a data structure allowing a short response time. In this paper, we extend the work of Amilhastre et al. [1] and Vempaty [15] by the use of a new structure, tree-driven automata, that takes advantage of the structural characteristics of configuration problems (decomposition of the components into independent subcomponents). Tree-driven automata can be far more compact than classical automata while keeping their good properties, especially a tractable complexity for the maintenance of global consistency.     

元胞自动机方法在MEMS工艺模拟中的应用

随着计算机技术的发展和MEMS(micro-electro-mechanical system)自身发展的需要,应用元胞自动机方法模拟MEMS加工工艺的研究发展迅速.首先,简要介绍了元胞自动机原理,然后,综述了元胞自动机方法在MEMS工艺模拟中的应用现状,分析了应用元胞自动机方法模拟MEMS加工工艺的前景和方向.     

基于元胞自动机的埃博拉药物配送系统设计

采用元胞自动机模型预测了西非36个地区埃博拉患者的未来人数,针对抗埃博拉病毒药物保质期较短的特点,根据所需药物数量设计出了该药物的二级配送系统,提出了最短时间配送系统、最低成本配送系统2种模型,并进一步阐述了运行效率更为高效的跨国界最低成本配送系统。更多还原     

拟（h,k）存贮有限自动机的可逆性

主要研究拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱可逆性,以及它的弱逆,得到了拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k＋1步弱可逆拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱逆。     

基于字频分布的中文网页编码识别算法

编码识别是网页内容过滤的必要前提,多种中文编码共存给中文网页的内容过滤带来不便。针对上述问题,提出一种基于字频分布的中文网页编码识别算法。根据汉字的使用频率,选取使用频度较高的字符构成高频字符编码表,以高频字符编码作为关键字,使用改进的模式匹配算法查找待识别网页,并统计匹配次数。将编码的匹配结果作为分析的依据,最终判定待识别网页的真实码制。实验结果证明,与Unigram算法相比,该算法对目前通用的中文编码识别率较高,适合对未知编码的中文网页进行快速编码识别。     

下推自动机的状态转换图与下推自动机的化简

参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——PAD 状态转换图,证明了下推自动机与标准下推自动机的等价性。给出了对标准下推自动机进行化简的原则,并给出了化简算法,实现了下推自动机的化简。     

时间自动机状态空间的一个极小化构造方法

对时间自动机的转换系统进行改进,提出了一个状态空间的极小化构造方法。该方法用位置和停留在该位置时的可能时钟值集合来表示状态,以此隐藏因时间流逝而引发的无穷状态,得到了改进的转换系统——时间段转换系统;并通过对转换可能发生时间的分析,去除无效转换;然后使用转换互模拟合并等价状态,实现了状态空间的极小化,有效地避免了状态空间爆炸。     

格值有限状态自动机的同态和商自动机

提出了格值有限状态自动机（LFSA）的同态、强同态的概念,研究了LFSAs同态、强同态的若干性质。在LFSAs强同态的基础上,得到了LFSA的商自动机及其最小化自动机,刻画了商自动机的性质。     

采用动作时序逻辑的Web服务组合方法

基于有限状态自动机理论,将Web服务建模成一个有限状态自动机。针对网络服务描述语言(WSDL)在服务行为描述方面的缺陷对其进行扩展,提出了从扩展的WSDL到动作时序逻辑(TLA)语言的转换算法,从而可以用TLA对服务行为进行形式化描述和规范,为描述Web服务提供了一个新的方法。讨论了在动作时序逻辑中,服务组合时各组件服务的有限状态自动机的组合方式,以及伴随着服务组合,单个服务的TLA规范如何组合以形成复合服务的TLA规范的问题,并在此基础上,提出了实现TLA规范正确组合的算法思想。