格值交替树自动机
作者:
作者单位:

作者简介:

魏秀娟(1990-),女,河南郑州人,博士,主要研究领域为计算智能,加权自动机;李永明(1966-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为计算智能,加权自动机理论,模型检测,量子计算与量子信息.

通讯作者:

李永明,E-mail:liyongm@snnu.edu.cn

中图分类号:

TP301

基金项目:

国家自然科学基金(11671244,11271237);高等学校博士学科点专项科研基金(20130202110001)


L-valued Alternating Tree Automata
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (11671244, 11271237); Research Fund for the Doctoral Program of Higher Education of China (20130202110001)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    交替(树)自动机因其本身关于取补运算的简洁性及其与非确定型(树)自动机的等价性,成为自动机与模型检测领域研究的一个新方向.在格值交替自动机与经典交替树自动机概念的基础上,引入格值交替树自动机的概念,并研究了格值交替树自动机的代数封闭性和表达能力.首先,证明了对格值交替树自动机的转移函数取对偶运算,终止权重取补之后所得自动机与原自动机接受语言互补这一结论.其次,证明了格值交替树自动机关于交、并运算的封闭性.最后,讨论了格值交替树自动机和格值树自动机、格值非确定型自动机的表达能力;证明了格值交替树自动机与格值树自动机的等价性,并给出了二者相互转化的算法及其复杂度分析;同时,提供了用格值非确定型自动机来模拟格值交替树自动机的方法.

    Abstract:

    Because of the simplicity of taking complement operation on alternating (tree) automata and the equivalence relationship between alternating (tree) automata and nondeterministic (tree) automata, the study on alternating (tree) automata becomes a new research area of automata and model checking. Based on notions of L-valued alternating automata and alternating tree automata, the notion of L-valued alternating tree automata is introduce, and closure properties and expressive power of L-valued alternating tree automata are studied. Firstly, it is proved that after taking dual operations on transitions and changing the weight of each final state to its complement, a new L-valued alternating tree automaton is achieved which is the complement of the starting one. Afterwards, the closure is illustrated under conjunction and disjunction of languages accepted by L-valued alternating tree automata. Finally, the expressive power of L-valued alternating tree automata, L-valued tree automata, and L-valued nondeterministic automata are discussed. The equivalence relationship is proved between L-valued alternating tree automata and L-valued tree automata, the algorithms are given between them and complexities are discussed of algorithms; simultaneously, a method is provided to show how to use L-valued nondeterministic automata to simulate L-valued alternating tree automata.

    参考文献
    相似文献
    引证文献
引用本文

魏秀娟,李永明.格值交替树自动机.软件学报,2019,30(12):3605-3621

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2016-09-18
  • 最后修改日期:2018-03-20
  • 录用日期:
  • 在线发布日期: 2019-12-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号