In the theory of formal languages, the pumping lemma for regular languages is a lemma that describes an essential property of all regular languages. Informally, it says that all sufficiently long strings in a regular language may be pumped—that is, have a middle section of the string repeated an arbitrary number of times—to produce a new string that is also part of the language. The pumping lemma is useful for proving that a specific language is not a regular language, by showing that the language does not have the property. Specifically, the pumping lemma says that for any regular language L {\displaystyle L} , there exists a constant p {\displaystyle p} such that any string w {\displaystyle w} in L {\displaystyle L} with length at least p {\displaystyle p} can be split into three substrings x {\displaystyle x} , y {\displaystyle y} and z {\displaystyle z} ( w = x y z {\displaystyle w=xyz} , with y {\displaystyle y} being non-empty), such that the strings x z , x y z , x y y z , x y y y z , . . . {\displaystyle xz,xyz,xyyz,xyyyz,...} are also in L {\displaystyle L} . The process of repeating y {\displaystyle y} zero or more times is known as "pumping". Moreover, the pumping lemma guarantees that the length of x y {\displaystyle xy} will be at most p {\displaystyle p} , thus giving a "small" substring x y {\displaystyle xy} that has the desired property. Languages with a finite number of strings vacuously satisfy the pumping lemma by having p {\displaystyle p} equal to the maximum string length in L {\displaystyle L} plus one. By doing so, no strings at all in L {\displaystyle L} have length at least p {\displaystyle p} . The pumping lemma was first proven by Michael Rabin and Dana Scott in 1959, and rediscovered shortly after by Yehoshua Bar-Hillel, Micha A. Perles, and Eli Shamir in 1961, as a simplification of their pumping lemma for context-free languages. == Formal statement == Let L {\displaystyle L} be a regular language. Then there exists an integer p ≥ 1 {\displaystyle p\geq 1} depending only on L {\displaystyle L} such that every string w {\displaystyle w} in L {\displaystyle L} of length at least p {\displaystyle p} ( p {\displaystyle p} is called the "pumping length") can be written as w = x y z {\displaystyle w=xyz} (i.e., w {\displaystyle w} can be divided into three substrings), satisfying the following conditions: | y | ≥ 1 {\displaystyle |y|\geq 1} | x y | ≤ p {\displaystyle |xy|\leq p} ( ∀ n ≥ 0 ) ( x y n z ∈ L ) {\displaystyle (\forall n\geq 0)(xy^{n}z\in L)} y {\displaystyle y} is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in L {\displaystyle L} ). (1) means the loop y {\displaystyle y} to be pumped must be of length at least one, that is, not an empty string; (2) means the loop must occur within the first p {\displaystyle p} characters. | x | {\displaystyle |x|} must be smaller than p {\displaystyle p} (conclusion of (1) and (2)), but apart from that, there is no restriction on x {\displaystyle x} and z {\displaystyle z} . In simple words, for any regular language L {\displaystyle L} , any sufficiently long string w {\displaystyle w} (in L {\displaystyle L} ) can be split into 3 parts, i.e. w = x y z {\displaystyle w=xyz} , such that all the strings x y n z {\displaystyle xy^{n}z} for n ≥ 0 {\displaystyle n\geq 0} are also in L {\displaystyle L} . Below is a formal expression of the pumping lemma. ∀ L ⊆ Σ ∗ , regular ( L ) ⟹ ∃ p ≥ 1 , ∀ w ∈ L , | w | ≥ p ⟹ ∃ x , y , z ∈ Σ ∗ , ( w = x y z ) ∧ ( | y | ≥ 1 ) ∧ ( | x y | ≤ p ) ∧ ( ∀ n ≥ 0 , x y n z ∈ L ) {\displaystyle {\begin{array}{l}\forall L\subseteq \Sigma ^{},{\mbox{regular}}(L)\implies \\\quad \exists p\geq 1,\forall w\in L,|w|\geq p\implies \\\qquad \exists x,y,z\in \Sigma ^{},(w=xyz)\land (|y|\geq 1)\land (|xy|\leq p)\land (\forall n\geq 0,xy^{n}z\in L)\end{array}}} == Use of the lemma to prove non-regularity == The pumping lemma is often used to prove that a particular language is non-regular: a proof by contradiction may consist of exhibiting a string (of the required length) in the language that lacks the property outlined in the pumping lemma. Example: The language L = { a n b n : n ≥ 0 } {\displaystyle L=\{a^{n}b^{n}:n\geq 0\}} over the alphabet Σ = { a , b } {\displaystyle \Sigma =\{a,b\}} can be shown to be non-regular as follows: Assume that some constant p ≥ 1 {\displaystyle p\geq 1} exists as required by the lemma. Let w {\displaystyle w} in L {\displaystyle L} be given by w = a p b p {\displaystyle w=a^{p}b^{p}} , which is a string longer than p {\displaystyle p} . By the pumping lemma, there must exist a decomposition w = x y z {\displaystyle w=xyz} with | x y | ≤ p {\displaystyle |xy|\leq p} and | y | ≥ 1 {\displaystyle |y|\geq 1} such that x y i z {\displaystyle xy^{i}z} in L {\displaystyle L} for every i ≥ 0 {\displaystyle i\geq 0} . Since | x y | ≤ p {\displaystyle |xy|\leq p} , the string y {\displaystyle y} only consists of instances of a {\displaystyle a} . Because | y | ≥ 1 {\displaystyle |y|\geq 1} , it contains at least one instance of the letter a {\displaystyle a} . Pumping y {\displaystyle y} to give x y 2 z {\displaystyle xy^{2}z} gives a word with more instances of the letter a {\displaystyle a} than the letter b {\displaystyle b} , since some instances of a {\displaystyle a} but none of b {\displaystyle b} were added. Therefore, x y 2 z {\displaystyle xy^{2}z} is not in L {\displaystyle L} which contradicts the pumping lemma. Therefore, L {\displaystyle L} cannot be regular. The proof that the language of balanced (i.e., properly nested) parentheses is not regular follows the same idea. Given p {\displaystyle p} , there is a string of balanced parentheses that begins with more than p {\displaystyle p} left parentheses, so that y {\displaystyle y} will consist entirely of left parentheses. By repeating y {\displaystyle y} , a string can be produced that does not contain the same number of left and right parentheses, and so they cannot be balanced. == Proof of the pumping lemma == For every regular language there is a finite-state automaton (FSA) that accepts the language. The number of states in such an FSA are counted and that count is used as the pumping length p {\displaystyle p} . For a string of length at least p {\displaystyle p} , let q 0 {\displaystyle q_{0}} be the start state and let q 1 , . . . , q p {\displaystyle q_{1},...,q_{p}} be the sequence of the next p {\displaystyle p} states visited as the string is emitted. Because the FSA has only p {\displaystyle p} states, within this sequence of p + 1 {\displaystyle p+1} visited states there must be at least one state that is repeated. Write q s {\displaystyle q_{s}} for such a state. The transitions that take the machine from the first encounter of state q s {\displaystyle q_{s}} to the second encounter of state q s {\displaystyle q_{s}} match some string. This string is called y {\displaystyle y} in the lemma, and since the machine will match a string without the y {\displaystyle y} portion, or with the string y {\displaystyle y} repeated any number of times, the conditions of the lemma are satisfied. For example, the following image shows an FSA. The FSA accepts the string: abcd. Since this string has a length at least as large as the number of states, which is four (so the total number of states that the machine passes through to scan abcd would be 5), the pigeonhole principle indicates that there must be at least one repeated state among the start state and the next four visited states. In this example, only q 1 {\displaystyle q_{1}} is a repeated state. Since the substring bc takes the machine through transitions that start at state q 1 {\displaystyle q_{1}} and end at state q 1 {\displaystyle q_{1}} , that portion could be repeated and the FSA would still accept, giving the string abcbcd. Alternatively, the bc portion could be removed and the FSA would still accept giving the string ad. In terms of the pumping lemma, the string abcd is broken into an x {\displaystyle x} portion a, a y {\displaystyle y} portion bc and a z {\displaystyle z} portion d. As a side remark, the problem of checking whether a given string can be accepted by a given nondeterministic finite automaton without visiting any state repeatedly, is NP hard. == General version of pumping lemma for regular languages == If a language L {\displaystyle L} is regular, then there exists a number p ≥ 1 {\displaystyle p\geq 1} (the pumping length) such that every string u w v {\displaystyle uwv} in L {\displaystyle L} with | w | ≥ p {\displaystyle |w|\geq p} can be written in the form u w v = u x y z v {\displaystyle uwv=uxyzv} with strings x {\displaystyle x} , y {\displaystyle y} and z {\displaystyle z} such that | x y | ≤ p {\displaystyle |xy|\leq p} , | y | ≥ 1 {\displaystyle |y|\geq 1} and u x y i z v {\displaystyle uxy^{i}zv} is in L {\displaystyle L} for every integer i ≥ 0 {\displaystyle i\geq 0} . From this, the above standard v
PANGU (software)
The PANGU (Planet and Asteroid Natural scene Generation Utility) is a computer graphics utility of which the development was funded by ESA and performed by University of Dundee. It generates scenes of planets, moons, asteroids, spacecraft and rovers. The main purpose of the tool is to test and validate navigation techniques based on the processing of images coming from on-board sensors, such as a camera or imaging LIDAR on a planetary lander.
Embedded analytics
Embedded analytics enables organisations to integrate analytics capabilities into their own, often software as a service, applications, portals, or websites. This differs from embedded software and web analytics (also commonly known as product analytics). This integration typically provides contextual insights, quickly, easily and conveniently accessible since these insights should be present on the web page right next to the other, operational, parts of the host application. Insights are provided through interactive data visualisations, such as charts, diagrams, filters, gauges, maps and tables often in combination as dashboards embedded within the system. This setup enables easier, in-depth data analysis without the need to switch and log in between multiple applications. Embedded analytics is also known as customer facing analytics. Embedded analytics is the integration of analytic capabilities into a host, typically browser-based, business-to-business, software as a service, application. These analytic capabilities would typically be relevant and contextual to the use-case of the host application. == History == The term "embedded analytics" was first used by Howard Dresner: consultant, author, former Gartner analyst and inventor of the term "business intelligence" said Howard Dresner while he was working for Hyperion Solutions, a company that Oracle bought in 2007. Oracle started then to use the term "embedded analytics" at their press release for Oracle Rapid Planning on 2009 . == Considerations with embedded analytics == When evaluating embedding analytics, consideration would normally be given to integration at various levels, these would likely include: security integration, data integration, application logic integration, business rules integration, and user experience integration. This is in contrast to traditional BI, which expects users to leave their workflow applications to look at data insights in a separate set of tools. This immediacy makes embedded analytics much more intuitive and likely to be valued by users. A December 2016 report from Nucleus Research found that using BI tools, which require toggling between applications, can take up as much as 1–2 hours of an employee's time each week, whereas embedded analytics eliminate the need to toggle between apps.
Omni-Path
Omni-Path Architecture (OPA) is a high-performance communication architecture developed by Intel. It aims for low communication latency, low power consumption and a high throughput. It directly competes with InfiniBand. Intel planned to develop technology based on this architecture for exascale computing. The current owner of Omni-Path is Cornelis Networks. == History == Production of Omni-Path products started in 2015 and delivery of these products started in the first quarter of 2016. In November 2015, adapters based on the 2-port "Wolf River" ASIC were announced, using QSFP28 connectors with channel speeds up to 100 Gbit/s. Simultaneously, switches based on the 48-port "Prairie River" ASIC were announced. First models of that series were available starting in 2015. In April 2016, implementation of the InfiniBand "verbs" interface for the Omni-Path fabric was discussed. In October 2016, IBM, Hewlett Packard Enterprise, Dell, Lenovo, Samsung, Seagate Technology, Micron Technology, Western Digital and SK Hynix announced a joint consortium called Gen-Z to develop an open specification and architecture for non-volatile storage and memory products—including Intel's 3D Xpoint technology—which might in part compete against Omni-Path. Intel offered their Omni-Path products and components via other (hardware) vendors. For example, Dell EMC offered Intel Omni-Path as Dell Networking H-series, following the naming-standard of Dell Networking in 2017. In July 2019, Intel announced it would not continue development of Omni-Path networks and canceled OPA 200 series (200-Gbps variant of Omni-Path). In September 2020, Intel announced that the Omni-Path network products and technology would be spun out into a new venture with Cornelis Networks. Intel would continue to maintain support for legacy Omni-Path products, while Cornelis Networks continues the product line, leveraging existing Intel intellectual property related to Omni-Path architecture. In 2021, Cornelis announced Omni-Path Express, which replaces PSM2-based drivers and middleware, which trace back to PathScale's PSM created in 2003, for the existing Omni-Path hardware, with a native libfabric provider.
Signatures with efficient protocols
Signatures with efficient protocols are a form of digital signature invented by Jan Camenisch and Anna Lysyanskaya in 2001. In addition to being secure digital signatures, they need to allow for the efficient implementation of two protocols: A protocol for computing a digital signature in a secure two-party computation protocol. A protocol for proving knowledge of a digital signature in a zero-knowledge protocol. In applications, the first protocol allows a signer to possess the signing key to issue a signature to a user (the signature owner) without learning all the messages being signed or the complete signature. The second protocol allows the signature owner to prove that he has a signature on many messages without revealing the signature and only a (possibly) empty subset of the messages. The combination of these two protocols allows for the implementation of digital credential and ecash protocols.
NASA AI Assisted-Air Quality Monitoring Project
The NASA Expert-System Ion Trap Mass Spectrometer (ES-ITMS) Project was a public-private partnership to develop an artificial intelligence assisted, air quality monitoring system and was qualified for use on the Space Shuttle. The partnership was also the first cost and intellectual property shared public-partnership implemented by NASA, which used the commercial Research and Development Limited Partnership (RDLP) model that had been adopted by the Reagan Administration for Department of Defense semiconductor development, and recommended for use by NASA for space commercialization. The project partners included NASA, the University of Florida and Finnigan MAT Corporation, was organized and administered by the NASA Joint Enterprise Institute (subsequently NASA Joint Sponsored Program) and ran from 1988 through 1990. The partnership concluded final testing in 1991, generating four patents, expert system software and application protocol reports. The system was space qualified for use on the Shuttle and elements of the ES-ITMS system were integrated into the product Improvements for Finnigan MAT corporation. The success of the partnership lead NASA to create a pilot program to develop partnership business models as an ongoing management practice. == Purpose and objectives == The need to monitor air quality in confined spaces represented an increasing challenge for NASA's planned space missions and private sector facility managers facing the increased scrutiny of possible air contaminants. Up to the early 1980's, air quality monitors generally required large spaces and human technicians to interpret readings. This created a need for miniaturized air quality monitors that could generate reliable and accurate analytic results without on-site technician presence. NASA initiated projects to develop..."mobile and/or portable mass spectrometers" that evaluated the "tradeoff between instrumentation capabilities and space, weight and power considerations." NASA selected a "commercial ITMS instrument capable of generating electron ionization, chemical ionization and mass spectrometry data", to develop a linked expert system to accomplish analysis without human intervention. The commercial instrumentation was from Finnigan MAT corporation while the scientific expertise to support expert system development was available at the University of Florida. The project managers at NASA Ames created a single, integrated project using the RDLP model with objectives to: Develop AI/expert system software for instrument control (NASA's role) Expand sensitivity, selectivity and speed of the spectrometer (Univ Florida role) Expand the spectrometer analytic capability and automate the screening (Finnigan role) == Membership == The partnership included seven specialists from five member organizations: Federal Government National Aeronautics and Space Administration (NASA) NASA Ames Research Center (ARC) NASA Kennedy Space Center (KSC) Commercial Finnigan MAT Corporation (Thermo-Fisher Scientific) TGS Technology, Inc. Research Management University of Florida == Organization, management and administration == The technical project was organized into two development teams, one located in at the NASA Ames Research Center covering expert systems and analytic capabilities and one in Florida covering improved sensitivity and testing. The partnership management and administration was provided by a non-profit, partnership support organization: the Joint Enterprise Institute operating through San Francisco State University Foundation (SFSUF) with a NASA employee liaison, Syed Shariq. == Public-private partnership == The partnership structure was as a prototype test of a pilot NASA program to develop public-private partnership business models. The pilot program was known as the NASA Joint Sponsored Research Program (JSRP), which operated as the NASA Joint Enterprise Institute between 1988 and 1991. The partnership was the first public-private, research and development partnership implemented by NASA in response to national policy shifts to increase technology transfer and space commercialization. The partnership structure included a two year technology development and testing plan that cost $610,000, of which NASA funded $310,000, Finnigan $175,000 and the University of Florida $95,000. == Results and commercialization == The project generated patents (4), software (2) and application protocol reports (8). NASA gained use of the patents and jointly development software while Finnigan received commercial utilization rights. The results were commercialized within eighteen months of project completion. == Recognition == NASA recognized the project as a space qualified instrument. Its achievements were reported to the NASA Administrator, directly leading to establishment of the agency-wide Joint Sponsored Research Program.
KLJN Secure Key Exchange
Random-resistor-random-temperature Kirchhoff-law-Johnson-noise key exchange, also known as RRRT-KLJN or simply KLJN, is an approach for distributing cryptographic keys between two parties that claims to offer unconditional security. This claim, which has been contested, is significant, as the only other key exchange approach claiming to offer unconditional security is Quantum key distribution. The KLJN secure key exchange scheme was proposed in 2005 by Laszlo Kish and Granqvist. It has the advantage over quantum key distribution in that it can be performed over a metallic wire with just four resistors, two noise generators, and four voltage measuring devices---equipment that is low-priced and can be readily manufactured. It has the disadvantage that several attacks against KLJN have been identified which must be defended against. "Given that the amount of effort and funding that goes into Quantum Cryptography is substantial (some even mock it as a distraction from the ultimate prize which is quantum computing), it seems to me that the fact that classic thermodynamic resources allow for similar inherent security should give one pause," wrote Henning Dekant, the founder of the Quantum Computing Meetup, in April 2013. The Cybersecurity Curricula 2017, a joint project of the Association for Computing Machinery, the IEEE Computer Society, the Association for Information Systems, and the International Federation for Information Processing Technical Committee on Information Security Education (IFIP WG 11.8) recommends teaching the KLJN Scheme as part of teaching "Advanced concepts" in its knowledge unit on cryptography. == See Also/Further Reading ==