α-words and the radix order
| Autor: | Hui-Ling Ho, Wai-Fong Chuan, Chun-Yu Chen, Fang-Yi Liao |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Lexicographic order
Sequence General Computer Science Existential quantification 0102 computer and information sciences 02 engineering and technology Function (mathematics) Lexicographical order 01 natural sciences Theoretical Computer Science Combinatorics α-word Radix order 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Order (group theory) 020201 artificial intelligence & image processing Function composition Radix Alphabet Mathematics |
| Zdroj: | Theoretical Computer Science. 412:876-891 |
| ISSN: | 0304-3975 |
| Popis: | Let @a=(a"1,a"2,...) be a sequence (finite or infinite) of integers with a"1>=0 and a"n>=1, for all n>=2. Let {a,b} be an alphabet. For n>=1, and r=r"1r"2...r"n@?N^n, with 0@?r"i@?a"i for 1@?i@?n, there corresponds an nth-order @a-word u"n[r] with label r derived from the pair (a,b). These @a-words are defined recursively as follows: u"-"1=b,u"0=a,u"1[r"1]=a^a^"^1^-^r^"^1ba^r^"^1,u"i[r"1r"2...r"i]=u"i"-"1[r"1r"2...r"i"-"1]^a^"^i^-^r^"^iu"i"-"2[r"1r"2...r"i"-"2]u"i"-"1[r"1r"2...r"i"-"1]^r^"^i,i>=2. Many interesting combinatorial properties of @a-words have been studied by Chuan. In this paper, we obtain some new methods of generating the distinct @a-words of the same order in lexicographic order. Among other results, we consider another function r@?w[r] from the set of labels of @a-words to the set of @a-words. The string r is called a new label of the @a-word w[r]. Using any new label of an nth-order @a-word w, we can compute the number of the nth-order @a-words that are less than w in the lexicographic order. With the radix orders |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect