无穷状态自动机序列，k-正则序列及相关问题的研究

发布时间：2018-03-24 01:33

  本文选题：自动机序列　切入点：正则序列　出处：《华中科技大学》2016年博士论文

【摘要】：本文主要研究了一类整数序列的正则性,并将有限字符集上的代换和有限自动机的概念推广到了无穷字符集上.同时研究了无穷字符集上的代换和无穷状态自动机所生成序列的正则性.最后研究了一类由Cantor-like序列生成sum-free集的一些性质,着重研究了它们的正则性.具体的说,我们研究了三类序列的正则性问题：第一类是序列.(「log6(an-β)」}n≥0的正则性刻画.我们利用语言的正则性,证明了序列{「log6(an-β)」}n≥0是正则的当且仅当α∈Q.第二类是由无穷字符集上的代换和无穷状态自动机所生成的序列.将其与有限字符集上的代换和有限自动机的性质进行比较,重点研究它们生成序列的正则性问题,以及在线性回归投影下正则性不变的等价刻画.己知取值有限的正则序列就是自动机序列这一结论,我们也给出了一种判断序列非自动机的准则.第三类则是由Cantor-like序列和一些特殊的代换序列所生成的sum-free集.这样的sum-free集可以被看作是整数序列.我们研究它们的正则性,并讨论了一类sum-free集所对应的0—1序列的自动机性质.令α,β∈R,b≥2是一个整数.Allouche和Shallit证明了序列[「an+β」}n≥0是6-正则的当且仅当a是有理数.在第三章,我们主要讨论了语言的正则性问题.利用给出的一类特殊的语言的正则性与基的变换无关的性质,证明了序列{11ogb(an+β)」}≥0的正则性的等价刻画,即它是正则的当且仅当α∈Q,这个结论不仅回答了Allouche和Shallit提出的问题,更是对这个问题的进一步扩展.在第四章,我们首先给出了关于无穷字符集上的代换和无穷状态自动机的定义和一些基本性质.然后重点研究了由它们生成的序列的正则性问题,并给出了产生一些非正则序列的条件.接下来给出了一类在线性回归投影下序列正则性的等价刻画.又根据正则序列和自动机序列之间的关系,间接给出了一个判断序列非自动机的准则.在本章的最后,给出了关于无穷状态自动机的一些基本拓展,并研究了由它生成序列的部分性质.Cameron介绍了在sum-free集合所有0—1序列构成的集合之间的一个双射.在第五章,我们首先给出了关于sum-free集的研究背景和研究现状.我们给出了一类由Cantor-like序列和一些特殊的代换序列所生成的自然数上的sum-free集,并且证明了这样生成的sum-free集是2-正则的.同时反过来考虑了一类特殊的sum-free集所对应的0—1序列的自动机性质.在最后一章,我们首先系统的总结了一下本文的主要结果,然后针对每个结果给出了说明以及进一步研究的方向.
[Abstract]:In this paper, we study the regularity of a class of integer sequences. The concepts of substitution and finite automaton on finite character set are extended to infinite character set. At the same time, the regularity of sequences generated by substitution and infinite state automata on infinite character set is studied. Some properties of generating sum-free sets from Cantor-like sequences, In this paper, we focus on their regularity. Specifically, we study the regularity of three classes of sequences: the first is the regularity characterization of sequence. ("log6an- 尾)"} n 鈮，

本文编号：1656140