On automatic infinite permutations
From MaRDI portal
Abstract: An infinite permutation is a linear ordering of . 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.
Recommendations
- On infinite permutations
- On periodicity and low complexity of infinite permutations
- scientific article; zbMATH DE number 3273200
- Infinite classes of generalised complete permutations
- scientific article; zbMATH DE number 1376752
- Automata on infinite biposets
- On the orders of elements of the group of automaton permutations
- Some problems on groups of finite automatic permutations
- On permutations generated by infinite binary words
- On the enumeration of permutominoes
Cites work
- Automatic Sequences
- Enumeration and decidable properties of automatic sequences
- Infinite permutations of lowest maximal pattern complexity
- On an infinite permutation similar to the Thue-Morse word
- On periodicity and low complexity of infinite permutations
- On permutations containing no long arithmetic progressions
- On permutations generated by infinite binary words
- On the infinite permutation generated by the period doubling word
- On the permutations generated by Sturmian words
- Periodicity, repetitions, and orbits of an automatic sequence
- Permutation complexity of the Thue-Morse word
- Suites algébriques, automates et substitutions
- Uniform tag sequences
Cited in
(10)- scientific article; zbMATH DE number 3862472 (Why is no real title available?)
- Infinite permutations vs. infinite words
- Orbit theory, locally finite permutations and Morse arithmetic
- Canonical representatives of morphic permutations
- On the permutation complexity of the Cantor-like sequences
- Homogeneous permutations
- On permutations generated by infinite binary words
- Permutations of \(\mathbb{N}\) generated by left-right filling algorithms
- Ordering sequences by permutation transducers
- On infinite permutations
This page was built for publication: On automatic infinite permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911428)
