Structures without Scattered-Automatic Presentation
Structures without Scattered-Automatic Presentation
复制标题
无分散自动呈现的结构
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Philipp Schlicht
中科院分区：
文献类型：
--
作者：
Alexander Kartzow;Philipp Schlicht
Bruyere和Carton将有限自动机阅读无限单词的概念提升到有限自动机阅读形状为任意线性顺序的单词。有限词自动机可以用来表示无限结构，即所谓的词自动结构。类似地，对于线性序\（\mathfrak{L}\），存在\（\mathfrak{L}\）-自动结构类。本文证明了有限凝聚秩为1 + α的固定\（\mathfrak {L}\）的\（\mathfrak{L}\）-自动结构类的以下限制。
Bruyere and Carton lifted the notion of finite automata reading infinite words to finite automata reading words with shape an arbitrary linear order \(\mathfrak{L}\). Automata on finite words can be used to represent infinite structures, the so-called word-automatic structures. Analogously, for a linear order \(\mathfrak{L}\) there is the class of \(\mathfrak{L}\)-automatic structures. In this paper we prove the following limitations on the class of \(\mathfrak{L}\)-automatic structures for a fixed \(\mathfrak{L}\) of finite condensation rank 1 + α.