Interleaving of path sets
Interleaving of path sets
复制标题
路径集的交错
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
D. Slonim
中科院分区：
文献类型：
--
作者：
W. Abram;J. Lagarias;D. Slonim
路集是有向标号图中从一个固定的初始顶点开始的单边无限游动所对应的单边无限符号序列空间。路集是单侧sofic移位的推广。本文研究抽取无穷等差数列（modn）中符号序列的抽取运算。从位置j处的符号开始。它还研究了一族n元交织操作，每个元n一个，其作用于有序集$（X_0，X_1，...，X_{n-1}）$上的单边符号序列，以产生所有输出序列的集合X$，所述输出序列是通过将每个$X_i$中的字$x_i$的符号以算术级数（mod n）交织而获得的。它研究了一组与交织和抽取相关的闭包运算。它回顾了基本的算法结果，介绍了路径集和存在一个最小的权利解决介绍。给出了由路集的表示计算路集的抽取表示的算法，证明了$psi_{j，n}（X）$的最小右分解表示至多比X的最小右分解表示多一个顶点.它表明，一个路径集只有1000个不同的抽取。证明了固定字母表上的路集类在所有交织运算下都是闭的，并给出了给定集合X_i的n重交织表示的计算算法。研究了交织分解，对具有无限交织分解的路径集进行了分类，并给出了识别算法。它显示了迭代交错分解过程的有限性，它“冻结”了具有无限交错的因子。
Path sets are spaces of one-sided infinite symbol sequences corresponding to the one-sided infinite walks beginning at a fixed initial vertex in a directed labeled graph. Path sets are a generalization of one-sided sofic shifts. This paper studies decimation operations $psi_{j, n}(cdot)$ which extract symbol sequences in infinite arithmetic progressions (mod n). starting with the symbol at position j. It also studies a family of n-ary interleaving operations, one for each arity n, which act on an ordered set $(X_0, X_1, ..., X_{n-1})$ of one-sided symbol sequences on a finite alphabet A, to produce a set $X$ of all output sequences obtained by interleaving the symbols of words $x_i$ in each $X_i$ in arithmetic progressions (mod n). It studies a set of closure operations relating interleaving and decimation. It reviews basic algorithmic results on presentations of path sets and existence of a minimal right-resolving presentation. It gives an algorithm for computing presentations of decimations of path sets from presentations of path sets, showing the minimal right-resolving presentation of $psi_{j,n}(X)$ has at most one more vertex than a minimal right-resolving presentation of X. It shows that a path set has only finitely many distinct decimations. It shows the class of path sets on a fixed alphabet is closed under all interleaving operations, and gives algorithms for computing presentations of n-fold interleavings of given sets $X_i$. It studies interleaving factorizations and classifies path sets that have infinite interleaving factorizations, and gives an algorithm to recognize them. It shows a finiteness of a process of iterated interleaving factorizations, which"freezes"factors that have infinite interleavings.