Ordering sequences by permutation transducers

详细信息    查看全文

• 作者：Wieb Bosma^a ; ^c ; ^{w.bosma@math.ru.nl} ; Hans Zantema^b ; ^a ; ^{h.zantema@tue.nl}
• 关键词：Automaton ; Sequence ; Transducer
• 刊名：Indagationes Mathematicae
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：28
• 期：1
• 页码：38-54
• 全文大小：279 K
• 卷排序：28

文摘

To extend a natural concept of equivalence of sequences to two-sided infinite sequences, the notion of permutation transducer is introduced. Requiring the underlying automaton to be deterministic in two directions, it provides the means to rewrite bi-infinite sequences. The first steps in studying the ensuing hierarchy of equivalence classes of bi-infinite sequences are taken, by describing the classes of ultimately periodic two-sided infinite sequences. It is important to make a distinction between unpointed and pointed sequences, that is, whether or not sequences are considered equivalent up to shifts. While one-sided ultimately periodic sequences form a single equivalence class under ordinary transductions, which is shown to split into two under permutation transductions, in the two-sided case there are three unpointed and seven pointed equivalence classes under permutation transduction.