Article presented at the 8th International Conference Words 2011 in Prague, Czech Republic. This article investigates the combinatorial complexity of infinite permutations on N associated with the image of uniformly recurrent aperiodic binary words under the letter doubling map.
The College of Science provides students with the high-demand skills and knowledge to succeed as researchers and professionals. The College includes four departments: Biology, Chemistry, Math, and Physics, and is also home to a number of interdisciplinary programs, centers, institutes, intercollegiate programs, labs, and services.
Article presented at the 8th International Conference Words 2011 in Prague, Czech Republic. This article investigates the combinatorial complexity of infinite permutations on N associated with the image of uniformly recurrent aperiodic binary words under the letter doubling map.
Physical Description
12 p.
Notes
Abstract: Given a countable set X (usually taken to be N or Z), an infinite permutation 𝜋 of X is a linear ordering ≺𝜋 of X, introduced in [6]. This paper investigates the combinatorial complexity of infinite permutations on N associated with the image of uniformly recurrent aperiodic binary words under the letter doubling map. An upper bound for the complexity is found for general words, and a formula for the complexity is established for the Sturmian words and the Thue-Morse word.
Publication Title:
Electronic Proceedings in Theoretical Computer Science
Volume:
63
Page Start:
265
Page End:
276
Collections
This article is part of the following collection of related materials.
UNT Scholarly Works
Materials from the UNT community's research, creative, and scholarly activities and UNT's Open Access Repository. Access to some items in this collection may be restricted.
