|
Automatic Sequence
In mathematics and theoretical computer science, an automatic sequence (also called a ''k''-automatic sequence or a ''k''-recognizable sequence when one wants to indicate that the base of the numerals used is ''k'') is an infinite sequence of terms characterized by a finite automaton. The ''n''-th term of an automatic sequence ''a''(''n'') is a mapping of the final state reached in a finite automaton accepting the digits of the number ''n'' in some fixed base ''k''.Allouche & Shallit (2003) p. 152Berstel et al (2009) p. 78 An automatic set is a set of non-negative integers ''S'' for which the sequence of values of its characteristic function χ''S'' is an automatic sequence; that is, ''S'' is ''k''-automatic if χ''S''(''n'') is ''k''-automatic, where χ''S''(''n'') = 1 if ''n'' \in ''S'' and 0 otherwise. Definition Automatic sequences may be defined in a number of ways, all of which are equivalent. Four common definitions are as follows. Automata-theore ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tag System
A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post–Turing machines)—briefly, a finite-state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition. Because all of the indicated operations are performed in a single transition, a tag machine strictly has only one state. Definitions A ''tag system'' is a triplet (''m'', ''A'', ''P''), where * ''m'' is a positive integer, called the ''deletion number''. * ''A'' is a finite alphabet of symbols, one of which is a special ''halting symbol''. All finite (possibly empty) strings on ''A'' are called ' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-regular Sequence
In mathematics and theoretical computer science, a ''k''-regular sequence is a sequence satisfying linear recurrence equations that reflect the base-''k'' representations of the integers. The class of ''k''-regular sequences generalizes the class of ''k''-automatic sequences to alphabets of infinite size. Definition There exist several characterizations of ''k''-regular sequences, all of which are equivalent. Some common characterizations are as follows. For each, we take ''R''′ to be a commutative Noetherian ring and we take ''R'' to be a ring containing ''R''′. ''k''-kernel Let ''k'' ≥ 2. The ''k-kernel'' of the sequence s(n)_ is the set of subsequences :K_(s) = \. The sequence s(n)_ is (''R''′, ''k'')-regular (often shortened to just "''k''-regular") if the R'-module generated by ''K''''k''(''s'') is a finitely-generated ''R''′-module.Allouche and Shallit (1992), Definition 2.1. In the special case when R' = R = \mathbb, the sequence s(n)_ is k-regular i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Unary Numeral System
The unary numeral system is the simplest numeral system to represent natural numbers: to represent a number ''N'', a symbol representing 1 is repeated ''N'' times. In the unary system, the number 0 (zero) is represented by the empty string, that is, the absence of a symbol. Numbers 1, 2, 3, 4, 5, 6, ... are represented in unary as 1, 11, 111, 1111, 11111, 111111, ... Unary is a Bijective numeration, bijective numeral system. However, because the value of a digit does not depend on its position, it is not a form of positional notation, and it is unclear whether it would be appropriate to say that it has a Radix, base (or "radix") of 1 (number), 1, as it behaves differently from all other bases. The use of tally marks in counting is an application of the unary numeral system. For example, using the tally mark | (𝍷), the number 3 is represented as |||. In East Asian cultures, the number 3 is represented as wikt:三#Translingual, 三, a character drawn with th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pumping Lemma For Regular Languages
Pumping may refer to: * The operation of a pump, for moving a liquid from one location to another **The use of a breast pump for extraction of milk * Pumping (audio), a creative misuse of dynamic range compression * Pumping (computer systems), the number of times data is transmitted per clock cycle * Pumping (oil well), injecting chemicals into a wellbore * Pumping (noise reduction), an unwanted artifact of some noise reduction systems * Pumping lemma, in the theory of formal languages * Gastric lavage, cleaning the contents of the stomach * Optical pumping, in which light is used to raise electrons from a lower energy level to a higher one * Pump (skateboarding), accelerating without pushing off of the ground * Pumping (My Heart), "Pumping" (My Heart), a 1976 song by Patti Smith Group {{disambiguation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cobham's Theorem
Cobham's theorem is a theorem in combinatorics on words that has important connections with number theory, notably transcendental numbers, and automata theory. Informally, the theorem gives the condition for the members of a set ''S'' of natural numbers written in bases ''b1'' and base ''b2'' to be recognised by finite automata. Specifically, consider bases ''b1'' and ''b2'' such that they are not powers of the same integer. Cobham's theorem states that ''S'' written in bases ''b1'' and ''b2'' is recognised by finite automata if and only if ''S'' is a finite union of arithmetic progressions. The theorem was proved by Alan Cobham in 1969 and has since given rise to many extensions and generalisations. Definitions Let n>0 be an integer. The representation of a natural number n in base b is the sequence of digits n_0n_1\cdots n_h such that : n=n_0+n_1b+\cdots+n_hb^h where 0\le n_0,n_1,\ldots,n_h 0. The word n_0n_1\cdots n_h is often denoted \langle n\rangle_b, or more simply, n_b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Multiplicative Independence
In number theory, two positive integers ''a'' and ''b'' are said to be multiplicatively independent if their only common integer power is 1. That is, for integers ''n'' and ''m'', a^n=b^m implies n=m=0. Two integers which are not multiplicatively independent are said to be multiplicatively dependent. As examples, 36 and 216 are multiplicatively dependent since 36^3=(6^2)^3=(6^3)^2=216^2, whereas 6 and 12 are multiplicatively independent. Properties Being multiplicatively independent admits some other characterizations. ''a'' and ''b'' are multiplicatively independent if and only if \log(a)/\log(b) is irrational. This property holds independently of the base of the logarithm. Let a = p_1^p_2^ \cdots p_k^ and b = q_1^q_2^ \cdots q_l^ be the canonical representations of ''a'' and ''b''. The integers ''a'' and ''b'' are multiplicatively dependent if and only if ''k'' = ''l'', p_i=q_i and \frac=\frac for all ''i'' and ''j''. Applications Büchi arithmet ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Academic Press
Academic Press (AP) is an academic book publisher founded in 1941. It was acquired by Harcourt, Brace & World in 1969. Reed Elsevier bought Harcourt in 2000, and Academic Press is now an imprint of Elsevier. Academic Press publishes reference books, serials and online products in the subject areas of: * Communications engineering * Economics * Environmental science * Finance * Food science and nutrition * Geophysics * Life sciences * Mathematics and statistics * Neuroscience * Physical sciences * Psychology Well-known products include the ''Methods in Enzymology'' series and encyclopedias such as ''The International Encyclopedia of Public Health'' and the ''Encyclopedia of Neuroscience''. See also * Akademische Verlagsgesellschaft (AVG) — the German predecessor, founded in 1906 by Leo Jolowicz (1868–1940), the father of Walter Jolowicz Walter may refer to: People * Walter (name), both a surname and a given name * Little Walter, American blues harmonica player Marion Wa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Morphic Word
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 c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Paperfolding Sequence
In mathematics the regular paperfolding sequence, also known as the dragon curve sequence, is an infinite sequence of 0s and 1s. It is obtained from the repeating partial sequence by filling in the question marks by another copy of the whole sequence. The first few terms of the resulting sequence are: If a strip of paper is folded repeatedly in half in the same direction, i times, it will get 2^i-1 folds, whose direction (left or right) is given by the pattern of 0's and 1's in the first 2^i-1 terms of the regular paperfolding sequence. Opening out each fold to create a right-angled corner (or, equivalently, making a sequence of left and right turns through a regular grid, following the pattern of the paperfolding sequence) produces a sequence of polygonal chains that approaches the dragon curve fractal: Properties The value of any given term t_n in the regular paperfolding sequence, starting with n=1, can be found recursively as follows. Divide n by two, as many times as possi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Baum–Sweet Sequence
In mathematics the Baum–Sweet sequence is an infinite automatic sequence of 0s and 1s defined by the rule: :''b''''n'' = 1 if the binary representation of ''n'' contains no block of consecutive 0s of odd length; :''b''''n'' = 0 otherwise; for ''n'' ≥ 0. For example, ''b''4 = 1 because the binary representation of 4 is 100, which only contains one block of consecutive 0s of length 2; whereas ''b''5 = 0 because the binary representation of 5 is 101, which contains a block of consecutive 0s of length 1. Starting at ''n'' = 0, the first few terms of the Baum–Sweet sequence are: :1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1 ... Historical motivation The properties of the sequence were first studied by Leonard E. Baum and Melvin M. Sweet in 1976. In 1949, Khinchin conjectured that there does not exist a non-quadratic algebraic real number having bounded partial quotients in its continued fraction expansion. A counterexample to this conjecture is still not known. Baum and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rudin–Shapiro Sequence
In mathematics, the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence, is an infinite 2-automatic sequence named after Marcel Golay, Walter Rudin, and Harold S. Shapiro, who independently investigated its properties. Definition Each term of the Rudin–Shapiro sequence is either 1 or -1. If the binary expansion of n is given by :n = \sum_ \epsilon_k(n) 2^k, then let :u_n = \sum_ \epsilon_k(n)\epsilon_(n). (So u_n is the number of times the block 11 appears in the binary expansion of n.) The Rudin–Shapiro sequence (r_n)_ is then defined by :r_n = (-1)^. Thus r_n = 1 if u_n is even and r_n = -1 if u_n is odd. The sequence u_n is known as the complete Rudin–Shapiro sequence, and starting at n = 0, its first few terms are: :0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... and the corresponding terms r_n of the Rudin–Shapiro sequence are: :+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, ... ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
