Matrix expression and reachability analysis of finite automata

In this paper,we propose a matrix-based approach for finite automata and then study the reachability conditions.Both the deterministic and nordeterministic automata are expressed in matrix forms,and th...     

特种车辆维修空间可达性评价方法研究

可达性作为维修性的定性指标,缺少定量评价的方法。传统方法只针对装备的整体进行定性评价,不能对不同的等级维修和单个维修动作进行评价。通过对维修性设计中的结构性因素进行分析,得到了空间可达性的主要影响因素。在虚拟维修仿真平台的基础上对工具旋转角度和作业空间比进行了量化评分,给出了针对维修作业过程中单个零部件拆卸的空间可达性评价方法。单个动作评价方法为等级维修的整体空间可达性评价提供了数据基础,并为新型特种车辆的维修方案论证和研制的空间可达性评价提供了手段。     

一种新的基于递归分解的图可达性查询算法

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.     

考虑出行方向的广州出租车时空可达性研究

出行方向是可达性研究中的一个关键要素, 因此, 提出一种考虑出行方向的出租车时空可达性分析方法。根据出租车经验路径分方向构建经验等级路网, 采用基于分层路网的Dijkstra算法计算得到各OD对之间的行程时间, 作为可达性评价指标, 并采用网格法和反距离加权插值法绘制得到广州市中心商业区等时线及其渲染图, 分方向、分时段对其时空可达性进行分析。结果证明了不同出行方向下, 特别是处于高峰时段, 可达性有较大的不同。     

RIAIL:大规模图上的可达性查询索引方法

图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据.     

启发式探索的协议测试序列生成

为避免可达性分析方法生成协议测试序列状态过程中爆炸问题的出现,提出了一种启发式探索协议状态格局空间的可执行测试序列生成算法. 该算法采用权值扩展有限状态机建模被测协议,以启发式状态格局探索策略替代传统的宽度优先搜索方式生成可执行协议测试序列;把协议可执行测试序列生成转化为在协议状态格局空间中探寻最小权值路径的问题. 实验数据表明,与宽度优先可达性分析方法相比,新算法具有较好的时空特性.     

居住小区价格与公共服务网络可达性的相关性研究

提出了居住小区公共服务网络的概念,考虑居住小区与各类公共服务节点之间的最短路径、最快路径、次短路径和次快路径等四个指标,以皮尔逊积矩相关系数评估各类公共服务节点可达性与居住小区住房价格的相关性,建立了计算模型,从而识别出对居住小区住房价格影响较大的因素,以武汉市居住小区公共服务网络为例进行了实证分析.结果表明,本方法能够效识别对居住小区价格有重要影响的公共服务要素,为居住小区规划和公共服务优化配置提供决策支持.     

BACH:线性混成系统有界可达性模型检验工具

混成自动机的模型检验问题非常困难,即使是其中相对简单的一个子类--线性混成自动机,它的可达性问题仍然是不可判定的.现有的相关工具大都使用多面体计算来判定线性混成自动机状态空间的可达集,复杂度高、效率低,无法解决实际应用规模的问题.描述了一个面向线性混成系统有界可达性模型检验工具--BACH(bounded reacha...     

对时间自动机中时钟约束的处理

在实时系统建模中,时间自动机是一个普便使用的工具,在求解状态可达性关系时对时钟约束的处理是关键,本文在分析已有理论的基础上提出了如何对含有不同时钟相互约束的系统处理.