检索结果-南通市图书馆

拟陷阱同步自动机的最短同步字的长度

引用

计算机科学 2012年第11期39卷 191-193页

作者：肖芬芳何勇胡斌梁王志喜湖南科技大学计算机科学与工程学院湘潭411201 湖南科技大学机电工程学院湘潭411201

既非陷阱也非强连通的同步自动机称为拟陷阱同步自动机。对于任意的拟陷阱同步自动机A,利用其强连通子自动机的状态数给出了A的最短同步字的长度的一个上界,进而获得了A满足C∨ern猜想的一个充分条件。

关键词：拟陷阱同步自动机陷阱同步自动机最短同步字强连通子自动机 C∨ern猜想

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

同步有界偏序自动机

引用

计算机学报 2019年第3期42卷 610-623页

作者：崔振河何勇孙士远湖南科技大学计算机科学与工程学院湖南湘潭411201

所有状态都能被同一个字转换到同一状态(完全确定有限状态)的自动机称为同步自动机.同步自动机在许多方面都有着广泛的应用,如重启装置的设计、系统测试、编码、工业自动化、机器人技术以及生物计算等.同步自动机研究的最基本的问题是... 详细信息

所有状态都能被同一个字转换到同一状态(完全确定有限状态)的自动机称为同步自动机.同步自动机在许多方面都有着广泛的应用,如重启装置的设计、系统测试、编码、工业自动化、机器人技术以及生物计算等.同步自动机研究的最基本的问题是自动机的同步性问题,同步性问题主要包括同步性检测和同步字查找.最短同步字问题是同步自动机研究的核心课题,关于这个问题,?erny提出了如下猜想:所有n-状态同步自动机的最短同步字长度的上确界为(n-1)~2.现有研究结果表明,对于某些特殊类型的自动机?erny猜想是成立的,例如循环自动机、欧拉自动机等.然而,对于一般的同步自动机?erny猜想尚未得到证实或否定.由于任何自动机都能看作偏序自动机,因而?erny猜想成立的充分必要条件是它对所有偏序自动机都成立.单演自动机和广义单演自动机等偏序自动机都已被证实满足?erny猜想.作为偏序自动机的另一类特殊情形,该文定义了有界偏序自动机,运用组合分析方法证明了n-状态有界偏序自动机最短同步字的长度为n-1.作为主要结果的推论,得出n-状态格序自动机的最短同步字的长度也是n-1.这就意味着有界偏序自动机(特别是格序自动机)满足?erny猜想.进一步地,该文设计了有界偏序自动机的同步性检测及同步字查找算法.最后,该文还对单演自动机、广义单演自动机和有界偏序自动机的关系进行了讨论,得出以下结论:广义单演自动机和有界偏序自动机同为单演自动机的真推广,且它们的表达能力不相容.

关键词：同步自动机最短同步字 Cerny猜想有界偏序自动机格序自动机

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

关于极端同步自动机的一些研究

关于极端同步自动机的一些研究

引用

作者：扈玉莹山东师范大学

学位级别：硕士

本文主要研究素数阶循环自动机和3,4-状态极端同步自动机,给出了素数阶循环自动机可扩张状态集的一些性质,定义了亏损字母和置换字母,并且通过讨论这两种字母在极端同步自动机中的存在情况,找出了包括现有的八种极端必要同步自动机在内... 详细信息

本文主要研究素数阶循环自动机和3,4-状态极端同步自动机,给出了素数阶循环自动机可扩张状态集的一些性质,定义了亏损字母和置换字母,并且通过讨论这两种字母在极端同步自动机中的存在情况,找出了包括现有的八种极端必要同步自动机在内的27种3,4-状态极端同步自动机.本文共分三章,具体内容如下:第一章:引言与预备知识.第二章:利用线性表示的方法简单地证明了n-状态循环自动机中所含状态数与n互素的子状态集都是n-可扩张的,并给出其最短同步字的一个具体形式,应用所得结论可以直接获得Pin关于素数阶同步循环自动机的结果.主要结论如下:定理2.2.1设A=(Q,∑,δ)是一个n-状态循环自动机,a是A的一个循环字母,&是A的一个亏损字母,P是Q的一个m阶非空真子集.如果(m,n)=1,那么P有一个形如bai(0≤i≤n-1)的扩张字.第三章:研究了3,4-状态极端同步自动机.对于3,4-状态极端同步自动机,首先分别给出了它们的部分公共特征,然后再根据所含置换字母的轨道数由少到多依次分析,最终得出了包括8种极端必要同步自动机在内的27种极端同步自动机.主要结论如下:定理3.2.1在同构意义下,3-状态极端同步自动机共有15个,其中有Fig.1中给出的4个极端必要同步自动机和Fig.1中未给出的11个极端非必要同步自动机.引理3.2.2设A=(Q,∑,δ)是一个3-状态极端同步自动机,且其中,∑1是所有置换字母的集合,∑2是所有1-亏损字母的集合,∑3是所有2-亏损字母的集合.则有以下结论成立:(1) ∑3 =(?), ∑2≠(?);(2)对任意的b∈∑2,有Qb2=Qb;(3) A有唯一的亏损状态;Q = {1,2,3}, E=∑1∪∑2∪E3,∑1 = {a1,a2,··· ,al}, ∑2={b1,b2,…,bm},∑3 ={c1,c2,· · ·,c?}.(4) ∑1≠(?).定理3.3.1在同构意义下,4-状态极端同步自动机共有12个,其中有Fig.1中给出的2个极端必要同步自动机和Fig.1中未给出的10个极端非必要同步自动机.引理3.3.2设A=(Q,∑,δ)是一个4-状态极端同步自动机,且其中,∑1是所有置换字母的集合,∑2是所有1-亏损字母的集合,∑3是所有2-亏损字母的集合,∑4是所有3-亏损字母的集合.则有以下结论成立:(1) ∑3 =(?), ∑4 =(?), ∑2≠(?);(2)对任意的b∈∑;2,有Qb2=Qb;(3) A有唯一的亏损状态;(4) ∑1≠(?).

关键词： (?)ern(?)猜想可扩张状态集最短同步字素数阶循环自动机置换字母亏损字母极端同步自动机

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

关于同步自动机和（？）ern（？）猜想的若干研究

关于同步自动机和（？）ern（？）猜想的若干研究

引用

作者：肖芬芳湖南科技大学

学位级别：硕士

同步自动机是一种特殊的有限状态自动机，在机器人学、工业自动化以及生物计算等方面有重要应用，同步性检测和最短同步字的长度(特别是(?)ern(?)猜想)是同步自动机理论研究的两个核心问题。研究同步自动机的常用方法是按照同步自动机... 详细信息

同步自动机是一种特殊的有限状态自动机，在机器人学、工业自动化以及生物计算等方面有重要应用，同步性检测和最短同步字的长度(特别是(?)ern(?)猜想)是同步自动机理论研究的两个核心问题。研究同步自动机的常用方法是按照同步自动机的结构特征进行分类，然后分析各类同步自动机的同步性检测问题，或者求解它们的最短同步字的长度，从而验证它们是否满足(?)ern(?)猜想。本文对拟陷阱同步自动机、C-型同步自动机和LC-型同步自动机进行了研究。对于任意一个拟陷阱同步自动机，利用它的强连通子自动机的状态数，给出了它的最短同步字的长度的一个上界，进而获得了它满足(?)ern(?)猜想的一系列充分条件。对于任意一个C-型自动机，利用模完全剩余系的特性，给出了它满足同步性的一个充分与必要条件，并且在它具有同步性时确定了它的最短同步字。对于任意一个LC-型同步自动机，通过分析它的同构自动机LCA的同步性，证明了LC-型同步自动机满足(?)ern(?)猜想。

关键词：同步自动机 (?)ern(?)猜想最短同步字拟陷阱同步自动机 Cn,i-型同步自动机 LC-型同步自动机

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：