On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

Line planning on tree networks with applications to the Quito Trolebús system

We discuss an optimization model for the line planning problem in public transport in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the computational complexity of this problem for tree network topologies as well as several categories of line operations that are important for the Quito Trolebús system. In practice, these instances can be solved quite well, and significant optimization potentials can be demonstrated.     

GF(3)上一类新型自缩控序列

设计GF(3)上一类新型的钟控模型,它由累积函数和钟控生成器复合生成。讨论这种模型所生成序列的数据率、周期、线性复杂度、1-重量复杂度等密码学性质。分析结果表明,生成的新序列具有数据率使用高、周期和线性复杂度较大等伪随机性,且该模型易于实现和推广,适合在通信密码中应用。     

一种最大向量平均个数的估计方法

提出一种估计n个d维向量中最大向量平均个数的方法。该方法通过分析单个向量与其他向量子集的支配关系,求出最大向量平均个数的解析式。证明解析式满足已知的递归关系,得到最大向量平均个数的近似估计。与已有方法相比,该方法可应用到估计k个其他向量支配的平均个数问题。     

网络流量预测方法

分析网络流量的行为特性并建立模型进行预测,对于网络管理以及安全预警具有重要意义。基于此,针对网络异常处理滞后、网络服务质量差等问题,研究多种经典流量预测方法,从流量特性、建模复杂性、预测精度及应用场景等多角度进行分析比较。实验结果证明,预测模型与具体场景密切相关,实际操作时需根据流量特性及预测目标选择合适的模型。     

改进Dijkstra算法在PGIS中的应用

传统Dijkstra算法用于路径诱导会使路网节点的数量增多、搜索范围扩大,从而耗费大量时间和空间,降低停车诱导信息系统(PGIS)的运行效率和实时性。针对城市路网的特定环境和路径诱导需求,根据2点之间直线最短的原理,在Dijkstra算法的基础上,提出一种应用于PGIS、基于矩形搜索范围的改进Dijkstra算法,设计并实现城市路网模型中单行、禁行、交叉点时间延误等问题的解决方案。实验结果表明,改进Dijkstra算法可以减少路网节点搜索范围和计算复杂度,提高用户搜索路径的实时性。     

基于优化策略的不确定数据流预测方法

为解决不确定数据流的预测问题,根据数据流高速、无限和动态不确定性的特点,在复杂人工智能预测和时间序列预测的基础上,提出一种基于优化策略的预测方法。综合考虑数据流中元组的不确定性与不确定异常性,以降低预测计算代价。同时考虑不确定的统计特性对卡尔曼滤波预测的影响,对Q和R进行异步优化估计,以形成最佳状态预测。实验结果表明,该方法的预测性能较好。     

Solving single-product economic lot-sizing problem with non-increasing setup cost,constant capacity and convex inventory cost in O(N log N) time

This paper considers an economic lot sizing model with constant capacity, non-increasing setup cost, and convex inventory cost function. Algorithms with computational time of O(N×TD_N)have been developed for solving the model, where N is the number of planning periods and TD_N is the total demand. This study partially characterizes the optimal planning structure of the model. A new efficient algorithm with computational time of O(N log N) has also been developed based on the partial optimal structure. Moreover, computational study demonstrates that the new algorithm is efficient.