|
Michael O. Rabin
Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician and computer scientist and a recipient of the Turing Award. Biography Early life and education Rabin was born in 1931 in Wrocław, Breslau, Weimar Republic, Germany (today Wrocław, in Poland), the son of a rabbi. In 1935, he Aliyah, emigrated with his family to Mandatory Palestine, Mandate Palestine. As a young boy, he was very interested in mathematics and his father sent him to the best high school in Haifa, where he studied under mathematician Elisha Netanyahu, who was then a high school teacher. Rabin graduated from the Hebrew Reali School in Haifa in 1948, and was drafted into the army during the 1948 Arab–Israeli War. The mathematician Abraham Fraenkel, who was a professor of mathematics in Jerusalem, intervened with the army command, and Rabin was discharged to study at the university in 1949. He received an M.Sc. from Hebrew University of Jerusal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Infinite-tree Automaton
In computer science and mathematical logic, an infinite-tree automaton is a state machine that deals with infinite tree structures. It can be seen as an extension of top-down finite-tree automata to infinite trees or as an extension of infinite-word automata to infinite trees. A finite automaton which runs on an infinite tree was first used by Michael Rabin for proving decidability of S2S, the monadic second-order theory with two successors. It has been further observed that tree automata and logical theories are closely connected and it allows decision problems in logic to be reduced into decision problems for automata. Definition Infinite-tree automata work on \Sigma-labeled trees. There are many slightly different definitions; here is one. A (nondeterministic) infinite-tree automaton is a tuple A = (\Sigma, D, Q, q_0, \delta, F ) with the following components. * \Sigma is an alphabet. This alphabet is used to label nodes of an input tree. * D\subset \mathbb is a finite ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Wrocław
Wrocław (; german: Breslau, or . ; Silesian German: ''Brassel'') is a city in southwestern Poland and the largest city in the historical region of Silesia. It lies on the banks of the River Oder in the Silesian Lowlands of Central Europe, roughly from the Baltic Sea to the north and from the Sudeten Mountains to the south. , the official population of Wrocław is 672,929, with a total of 1.25 million residing in the metropolitan area, making it the third largest city in Poland. Wrocław is the historical capital of Silesia and Lower Silesia. Today, it is the capital of the Lower Silesian Voivodeship. The history of the city dates back over a thousand years; at various times, it has been part of the Kingdom of Poland, the Kingdom of Bohemia, the Kingdom of Hungary, the Habsburg monarchy of Austria, the Kingdom of Prussia and Germany. Wrocław became part of Poland again in 1945 as part of the Recovered Territories, the result of extensive border changes and expulsions ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rabin Signature Algorithm
In cryptography, the Rabin signature algorithm is a method of digital signature originally proposed by Michael O. Rabin in 1978. The Rabin signature algorithm was one of the first digital signature schemes proposed. By introducing the use of hashing as an essential step in signing, it was the first design to meet what is now the modern standard of security against forgery, existential unforgeability under chosen-message attack, assuming suitably scaled parameters. Rabin signatures resemble RSA signatures with 'exponent e=2', but this leads to qualitative differences that enable more efficient implementation and a security guarantee relative to the difficulty of integer factorization, which has not been proven for RSA. However, Rabin signatures have seen relatively little use or standardization outside IEEE P1363 in comparison to RSA signature schemes such as RSASSA-PKCS1-v1_5 and RSASSA-PSS. Definition The Rabin signature scheme is parametrized by a randomized hash functio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Randomized Algorithms
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables. One has to distinguish between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite (Las Vegas algorithms, for example Quicksort), and algorithms which have a chance of producing an incorrect result (Monte Carlo algorithms, for example the Monte Carlo algorithm for the MFAS problem) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem. In common practice, randomized algor ... [...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] |
Probabilistic Automaton
In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the nondeterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix. Thus, the probabilistic automaton also generalizes the concepts of a Markov chain and of a subshift of finite type. The languages recognized by probabilistic automata are called stochastic languages; these include the regular languages as a subset. The number of stochastic languages is uncountable. The concept was introduced by Michael O. Rabin in 1963; a certain special case is sometimes known as the Rabin automaton (not to be confused with the subclass of ω-automata also referred to as Rabin automata). In recent years, a variant has been formulated in terms of quantum probabilities, the quantum finite automaton. Informal Description For a given initial state and input character, a deterministic finite automaton (DFA) has exactly on ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nondeterministic Finite Automata
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is ''uniquely'' determined by its source state and input symbol, and * reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is ''not'' a DFA, but not in this article. Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language. Like DFAs, NFAs only recognize regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
S2S (mathematics)
In mathematics, S2S is the monadic second order theory with two successors. It is one of the most expressive natural decidable theories known, with many decidable theories interpretable in S2S. Its decidability was proved by Rabin in 1969. Basic properties The first order objects of S2S are finite binary strings. The second order objects are arbitrary sets (or unary predicates) of finite binary strings. S2S has functions ''s''→''s''0 and ''s''→''s''1 on strings, and predicate ''s''∈''S'' (equivalently, ''S''(''s'')) meaning string ''s'' belongs to set ''S''. Some properties and conventions: * By default, lowercase letters refer to first order objects, and uppercase to second order objects. * The inclusion of sets makes S2S second order, with "monadic" indicating absence of ''k''-ary predicate variables for ''k''>1. * Concatenation of strings ''s'' and ''t'' is denoted by ''st'', and is ''not'' generally available in S2S, not even ''s''→0''s''. The prefix relation be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hyper-encryption
Hyper-encryption is a form of encryption invented by Michael O. Rabin which uses a high-bandwidth source of public random bits, together with a secret key that is shared by only the sender and recipient(s) of the message. It uses the assumptions of Ueli Maurer's bounded-storage model as the basis of its secrecy. Although everyone can see the data, decryption by adversaries without the secret key is still not feasible, because of the space limitations of storing enough data to mount an attack against the system. Unlike almost all other cryptosystems except the one-time pad, hyper-encryption can be proved to be information-theoretically secure, provided the storage bound cannot be surpassed. Moreover, if the necessary public information cannot be stored at the time of transmission, the plaintext can be shown to be impossible to recover, regardless of the computational capacity available to an adversary in the future, even if they have access to the secret key at that future time. A ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Miller–Rabin Primality Test
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test. It is of historical significance in the search for a polynomial-time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known. Gary L. Miller discovered the test in 1976; Miller's version of the test is deterministic, but its correctness relies on the unproven extended Riemann hypothesis. Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm in 1980. Mathematical concepts Similarly to the Fermat and Solovay–Strassen tests, the Miller–Rabin primality test checks whether a specific property, which is known to hold for prime values, holds for the number under testing. Strong probable primes The property is the follow ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Berlekamp–Rabin Algorithm
In number theory, Berlekamp's root finding algorithm, also called the Berlekamp–Rabin algorithm, is the probabilistic method of finding roots of polynomials over a field \mathbb Z_p. The method was discovered by Elwyn Berlekamp in 1970 as an auxiliary to the algorithm for polynomial factorization over finite fields. The algorithm was later modified by Rabin for arbitrary finite fields in 1979. The method was also independently discovered before Berlekamp by other researchers. History The method was proposed by Elwyn Berlekamp in his 1970 work on polynomial factorization over finite fields. His original work lacked a formal correctness proof and was later refined and modified for arbitrary finite fields by Michael Rabin. In 1986 René Peralta proposed a similar algorithm for finding square roots in \mathbb Z_p. In 2000 Peralta's method was generalized for cubic equations. Statement of problem Let p be an odd prime number. Consider the polynomial f(x) = a_0 + a_1 x + \cdots + ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
