期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到2篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
两个参数化匹配计数问题的难度分析
1
作者 韦立 许道云 王晓峰 《广西师范大学学报（自然科学版）》 CAS 北大核心 2011年第1期38-42,共5页
匹配计数问题是一个著名的难问题,考虑它的两个参数化问题p-deg-#MATCHING与p-#MATCHING,证明了p-deg-#MATCHING是固定参数易解的,p-#MATCHING有固定参数易解随机近似方案。
关键词 参数化 计数匹配问题 固定参数易解 随机近似方案
下载PDF
非确定有限自动机的最短D1-同步字求解 被引量：1
2
作者 朱凯 毋国庆 +1 位作者 袁梦霆 杨磊 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2021年第2期68-73,共6页
研究了非确定有限自动机的最短D1-同步字的计算问题。针对这种自动机定义了D1W问题及其参数化版本问题p-D1W和最优问题shortest-p-D1W,证明了p-D1W和shortest-p-D1W分别属于para-NP和para-DP。利用均匀分布模型随机生成大量的非确定的... 研究了非确定有限自动机的最短D1-同步字的计算问题。针对这种自动机定义了D1W问题及其参数化版本问题p-D1W和最优问题shortest-p-D1W,证明了p-D1W和shortest-p-D1W分别属于para-NP和para-DP。利用均匀分布模型随机生成大量的非确定的有限自动机进行实验,结果表明:在定长的参数下几乎所有随机产生的自动机实例都不是D1-可同步的,一旦将自动机上每个状态和字母的变迁函数的像数量限制在2以内,会出现少量的D1-可同步的自动机,且绝大多数最短同步字长不超过状态数的2倍。 展开更多
关键词 非确定有限自动机 同步字 固定参数易解的归约 可满足问题 参数化复杂性 参数化算法
原文传递
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部