主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
朱凯,毋国庆,吴理华,袁梦霆.有关时间自动机重置的若干问题的计算复杂性.软件学报,2019,30(7):0
有关时间自动机重置的若干问题的计算复杂性
On Computational Complexity of Several Problems for Resetting Timed Automata
投稿时间:2018-07-15  修订日期:2018-09-28
DOI:10.13328/j.cnki.jos.005757
中文关键词:  时间自动机  重置序列  归约  计算复杂性
英文关键词:timed auotmata  reset squences  reduction  computational complexity
基金项目:国家自然科学基金(61472146,61640221,61872272);广东省自然科学基金(2015A030313413)
作者单位E-mail
朱凯 武汉大学 计算机学院, 湖北 武汉 430072
华南农业大学 数学与信息学院, 广东 广州 510642 
 
毋国庆 武汉大学 计算机学院, 湖北 武汉 430072  
吴理华 华南农业大学 数学与信息学院, 广东 广州 510642  
袁梦霆 武汉大学 计算机学院, 湖北 武汉 430072 ymt@whu.edu.cn 
摘要点击次数: 130
全文下载次数: 94
中文摘要:
      自动机的重置序列也称同步序列,具有以下特性:有限自动机通过运行重置序列w,可从任意一个未知的或无法观测到的状态q0到达某个特定状态qw.这仅依赖于w,而与开始运行w时的状态q0无关.这一特性可用于部分可观察的复杂系统的自动恢复,而无需重启,甚至有时不能重启.于是重置问题自出现以来得到关注和持续研究.最近几年,它被扩展到可以描述诸如分布式、嵌入式实时系统等复杂系统的无限状态模型上,比如时间自动机和寄存器自动机等.本文以时间自动机的重置问题的计算复杂性为研究对象,发现重置问题与可达性问题有着紧密的联系.主要贡献是:(1)利用时间自动机可达性问题的最新成果,完善完全的确定的时间自动机重置问题的计算复杂性结论;(2)对部分规约的确定的时间自动机,研究得出即使在输入字母表大小减至2的情况下,其复杂性仍是PSPACE-完全的;特别地,在单时钟情况下是NLOGSPACE-完全的;(3)对完全的非确定的时间自动机,研究得出其Di-可重置问题(i=1,2,3)是不可判定的;其重置问题与非确定的寄存器自动机重置问题在指数时间可以相互归约,通过证明指数时间归约相对高复杂性类具有封闭性,利用非确定的寄存器自动机的结论得出单时钟的时间自动机的重置问题是Ackermann-完全的、限界的重置问题是NEXPTIME-完全的.这些复杂性结论说明关于时间自动机的重置问题大都是难解的,一方面为时间系统的可重置性的检测和求解奠定坚实的理论基础,另一方面为以后寻找具有高效算法的特殊结构的时间系统(即具有高效算法的问题子类)给予理论指导.
英文摘要:
      The reset sequences of finite automata,also known as the synchronizing sequences,have a characteristic:a finite automaton can reach a certain state qw by running a reset sequence from any unknown or unobservable state q0.This is dependent only on the reset sequence w itself,not on the state q0 of the finite automaton at the beginning of running the sequence w.It can be used to restore the running partially observable and complex systems automatically that needs no resetting,and sometimes even that cannot reset.Therefore,the reset problem has been paid attention to since it emerged and it has been studied continuously.Recently it has extended to infinite state models that can describe the complex systems,including distributed and embedded real-time systems,such as timed automata and register automata,etc.In this paper the computational complexity of several problems for the resetting timed automata is studied,and the strong connection between resettability problem and reachability problem for timed automata is found.Our main contribution includes:(1) the complexity of the problem for resetting the complete and deterministic timed automata is updated more precisely with the recent achievements in reachability problem for timed automata;(2) the complexity of the problem for resetting the partially specified timed automata is studied.Even if the size of input alphabet is decreased to 2 it is still PSPACE-complete,and in the case of single clock it is NLOGSPACE-complete;(3) for the complete and nondeterministic timed automata,Di-resetting problems (i=1,2,3) are all undecidable.And the resetting problem for nondeterministic register automata and nondeterministic timed automata can be inter-reduced in exponential time,and the reduction in exponential time is closed for relatively high computational complexity classes.So it concludes that the problem for resetting it in single clock case is Ackermann-complete,and that bounded version is NEXPTIME-complete from the results on corresponding nondeterministic register automata.These conclusions show that most of resetting problems for timed automata are intractable.On the one hand,they make a solid theoretical foundation for checking and solving the resettability of the timed systems,on the other hand,they guide to seek for some subclasses of real time system which have particular structure and effective algorithms for solving it.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利