INFINITE LYNDON WORDS

被引：36

作者：

SIROMONEY, R

MATHEW, L

DARE, VR

SUBRAMANIAN, KG

机构：

[1] Department of Mathematics, Madras Christian College, Madras, 600 059, Tambaran

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 50卷 / 02期

关键词：

LYNDON WORDS; INFINITE WORDS; QUEUE AUTOMATA; FORMAL LANGUAGES;

D O I：

10.1016/0020-0190(94)90016-7

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We define an infinite Lyndon word as the limit of an increasing sequence of prefix preserving Lyndon words and show that some of the interesting properties of Lyndon words generalize to the infinite case. We construct a queue automaton that recognizes the set of Lyndon words and show that it can be extended to recognize infinite Lyndon words. We discuss certain topological properties of the set of infinite Lyndon words such as homeomorphism with a subspace of the Cantor space.

引用

页码：101 / 104

页数：4