On automatic infinite permutations

Details On automatic infinite permutations On automatic infinite permutations

2011-09-28

arxiv.org/abs/1109.6131v1

Computer Science

Discrete Mathematics

Reported at Journ\'ees Montoises 2010; accepted to RAIRO ITA

Scientific paper

An infinite permutation $\alpha$ is a linear ordering of $\mathbb N$. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we shall show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships between these definitions and prove that they constitute a chain of inclusions. We also construct and study an automaton generating the Thue-Morse permutation.

Affiliated with

Also associated with

No associations

Rating

On automatic infinite permutations 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 On automatic infinite permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On automatic infinite permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-43211