|
Thue–Morse Sequence
In mathematics, the Thue–Morse or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of 0s and 1s) that can be obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. It is sometimes called the fair share sequence because of its applications to fair division or parity sequence. The first few steps of this procedure yield the strings 0, 01, 0110, 01101001, 0110100110010110, and so on, which are the prefixes of the Thue–Morse sequence. The full sequence begins: :01101001100101101001011001101001.... The sequence is named after Axel Thue, Marston Morse and (in its extended form) Eugène Prouhet. Definition There are several equivalent ways of defining the Thue–Morse sequence. Direct definition To compute the ''n''th element ''tn'', write the number ''n'' in binary. If the number of ones in this binary expansion is odd then ''tn'' = 1, if even then ''tn'' = 0. Th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Free Monoid
In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set ''A'' is usually denoted ''A''∗. The free semigroup on ''A'' is the sub semigroup of ''A''∗ containing all elements except the empty string. It is usually denoted ''A''+./ref> More generally, an abstract monoid (or semigroup) ''S'' is described as free if it is isomorphic to the free monoid (or semigroup) on some set. As the name implies, free monoids and semigroups are those objects which satisfy the usual universal property defining free objects, in the respective categories of monoids and semigroups. It follows that every monoid (or semigroup) arises as a homomorphic image of a free monoid (or semigroup). ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prolongable Morphism
In mathematics and computer science, a morphic word or substitutive word is an infinite sequence of symbols which is constructed from a particular class of endomorphism of a free monoid. Every automatic sequence is morphic. Definition Let ''f'' be an endomorphism of the free monoid ''A''∗ on an alphabet ''A'' with the property that there is a letter ''a'' such that ''f''(''a'') = ''as'' for a non-empty string ''s'': we say that ''f'' is prolongable at ''a''. The word : a s f(s) f(f(s)) \cdots f^(s) \cdots \ is a pure morphic or pure substitutive word. Note that it is the limit of the sequence ''a'', ''f''(''a''), ''f''(''f''(''a'')), ''f''(''f''(''f''(''a''))), ... It is clearly a fixed point of the endomorphism ''f'': the unique such sequence beginning with the letter ''a''.Lothaire (2011) p. 10Honkala (2010) p.505 In general, a morphic word is the image of a pure morphic word under a coding, that is, a morphism that maps letter to letter. If a morphic word is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fixed Point (mathematics)
In mathematics, a fixed point (sometimes shortened to fixpoint), also known as an invariant point, is a value that does not change under a given transformation (mathematics), transformation. Specifically, for function (mathematics), functions, a fixed point is an element that is mapped to itself by the function. Any set of fixed points of a transformation is also an invariant set. Fixed point of a function Formally, is a fixed point of a function if belongs to both the domain of a function, domain and the codomain of , and . In particular, cannot have any fixed point if its domain is disjoint from its codomain. If is defined on the real numbers, it corresponds, in graphical terms, to a curve in the Euclidean plane, and each fixed-point corresponds to an intersection of the curve with the line , cf. picture. For example, if is defined on the real numbers by f(x) = x^2 - 3 x + 4, then 2 is a fixed point of , because . Not all functions have fixed points: for example, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Monoid Morphism
In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being . Monoids are semigroups with identity. Such algebraic structures occur in several branches of mathematics. The functions from a set into itself form a monoid with respect to function composition. More generally, in category theory, the morphisms of an object to itself form a monoid, and, conversely, a monoid may be viewed as a category with a single object. In computer science and computer programming, the set of strings built from a given set of characters is a free monoid. Transition monoids and syntactic monoids are used in describing finite-state machines. Trace monoids and history monoids provide a foundation for process calculi and concurrent computing. In theoretical computer science, the study of monoids is fundamental for automata theory ( Krohn–Rh ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Squarefree Word
In combinatorics, a square-free word is a word (a sequence of symbols) that does not contain any squares. A square is a word of the form , where is not empty. Thus, a square-free word can also be defined as a word that avoids the pattern . Finite square-free words Binary alphabet Over a binary alphabet \, the only square-free words are the empty word \epsilon,0,1,01,10,010, and 101. Ternary alphabet Over a ternary alphabet ''\'', there are infinitely many square-free words. It is possible to count the number c(n) of ternary square-free words of length . This number is bounded by c(n) = \Theta(\alpha^n) , where 1.3017597 in \Sigma_ uniformly at random set \chi_w to ''w /math>'' followed by all other letters of \Sigma_ in increasing order set the number of iterations to 0 while , w, to the end of update \chi_w shifting the first elements to the right and setting \chi_w = a increment by if ends with a square of rank then ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Palindromic Number
A palindromic number (also known as a numeral palindrome or a numeric palindrome) is a number (such as 16361) that remains the same when its digits are reversed. In other words, it has reflectional symmetry across a vertical axis. The term ''palindromic'' is derived from palindrome, which refers to a word (such as ''rotor'' or ''racecar'') whose spelling is unchanged when its letters are reversed. The first 30 palindromic numbers (in decimal) are: : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ... . Palindromic numbers receive most attention in the realm of recreational mathematics. A typical problem asks for numbers that possess a certain property ''and'' are palindromic. For instance: * The palindromic primes are 2, 3, 5, 7, 11, 101, 131, 151, ... . * The palindromic square numbers are 0, 1, 4, 9, 121, 484, 676, 10201, 12321, ... . In any base there are infinitely many palindromic numbers, since ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Periodic Sequence
In mathematics, a periodic sequence (sometimes called a cycle or orbit) is a sequence for which the same terms are repeated over and over: :''a''1, ''a''2, ..., ''a''''p'', ''a''1, ''a''2, ..., ''a''''p'', ''a''1, ''a''2, ..., ''a''''p'', ... The number ''p'' of repeated terms is called the period ( period). Definition A (purely) periodic sequence (with period ''p''), or a ''p-''periodic sequence, is a sequence ''a''1, ''a''2, ''a''3, ... satisfying :''a''''n''+''p'' = ''a''''n'' for all values of ''n''. If a sequence is regarded as a function whose domain is the set of natural numbers, then a periodic sequence is simply a special type of periodic function. The smallest ''p'' for which a periodic sequence is ''p''-periodic is called its least period or exact period. Examples Every constant function is 1-periodic. The sequence 1,2,1,2,1,2\dots is periodic with least period 2. The sequence of digits in the decimal expansion of 1/7 is periodic with pe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Uniformly Recurrent Word
In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely many times.Lothaire (2011) p. 30Allouche & Shallit (2003) p.325Pytheas Fogg (2002) p.2 An infinite word is recurrent if and only if it is a sesquipower.Lothaire (2011) p. 141Berstel et al (2009) p.133 A uniformly recurrent word is a recurrent word in which for any given factor ''X'' in the sequence, there is some length ''n''''X'' (often much longer than the length of ''X'') such that ''X'' appears in ''every'' block of length ''n''''X''.Berthé & Rigo (2010) p.7Allouche & Shallit (2003) p.328 The terms minimal sequencePytheas Fogg (2002) p.6 and almost periodic sequence (Muchnik, Semenov, Ushakov 2003) are also used. Examples * The easiest way to make a recurrent sequence is to form a periodic sequence, one where the sequence repeats entirely after a given number ''m'' of steps. Such a sequence is then uniformly recurrent and ''n''''X'' can be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Critical Exponent Of A Word
In mathematics and computer science, the critical exponent of a finite or infinite sequence of symbols over a finite alphabet describes the largest number of times a contiguous subsequence can be repeated. For example, the critical exponent of "Mississippi" is 7/3, as it contains the string "ississi", which is of length 7 and period 3. If ''w'' is an infinite word over the alphabet ''A'' and ''x'' is a finite word over ''A'', then ''x'' is said to occur in ''w'' with exponent α, for positive real α, if there is a factor ''y'' of ''w'' with ''y'' = ''x''''a''''x''0 where ''x''0 is a prefix of ''x'', ''a'' is the integer part of α, and the length , ''y'', = α , ''x'', : we say that ''y'' is an ''α-power''. The word ''w'' is ''α-power-free'' if it contains no factors which are β-powers for any β ≥ α. p.281 The ''critical exponent'' for ''w'' is the supremum of the α for which ''w'' has α-powers,Berstel et al (2009) p.126 or equivalently the infimum of the α for whic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bitwise Negation
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor. Most bitwise operations are presented as two-operand instructions where the result replaces one of the input operands. On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition. While modern processors usually perform addition and multiplication just as fast as bitwise operations due to their longer instruction pipelines and other architectural design choices, bitwise operations do commonly use less power because of the reduced use of resources. Bitwise operators In the explanations below, any indication of a bit's position is counted from the right (least si ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
