Infinite permutations of lowest maximal pattern complexity

Details Infinite permutations of lowest maximal pattern complexity Infinite permutations of lowest maximal pattern complexity

2009-10-29

arxiv.org/abs/0910.5696v2

Mathematics

Combinatorics

Announced at WORDS 2009 in Salerno, to be submitted to the special issue of TCS

Scientific paper

An infinite permutation is a linear ordering of the set of non-negative integers. Generally, the properties of infinite permutations analogous to those of infinite words show some resemblances and some differences between permutations and words. In this paper, we define maximal pattern complexity for infinite permutations and show that this complexity function is ultimately constant if and only if the permutation is ultimately periodic. Then we characterize the non-periodic permutations of minimal complexity (equal to n) and find that they all are constructed with the use of Sturmian words.

Affiliated with

Also associated with

No associations

Rating

Infinite permutations of lowest maximal pattern complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Infinite permutations of lowest maximal pattern complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinite permutations of lowest maximal pattern complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-405465