Classifying Non-periodic Sequences by Permutation Transducers

被引：1

作者：

Zantema, Hans ^{[1
,2
]}

Bosma, Wieb ^{[2
,3
]}

机构：

[1] TU Eindhoven, Dept Comp Sci, POB 513, NL-5600 MB Eindhoven, Netherlands

[2] Radboud Univ Nijmegen, POB 9010, NL-6500 GL Nijmegen, Netherlands

[3] Ctr Wiskunde & Informat, Amsterdam, Netherlands

来源：

DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017 | 2017年 / 10396卷

关键词：

Compendex;

D O I：

10.1007/978-3-319-62809-7_28

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Transducers order infinite sequences into natural classes, but permutation transducers provide a finer classification, respecting certain changes to finite segments. We investigate this hierarchy for non-periodic sequences over {0, 1} in which the groups of 0s and 1s grow according to simple functions like polynomials. In this hierarchy we find infinite strictly ascending chains of sequences, all being equivalent with respect to ordinary transducers.

引用

页码：365 / 377

页数：13