Springpad was a free online application and web service that allowed its registered users to save, organize and share collected ideas and information. As users added content to their Springpad accounts, the application automatically identified and categorized it, then generated additional snippets based on the types of objects added—for example, listing price comparisons for products and showtimes for movies. Springpad was also available as apps on the iPad, iPhone and Android that synchronized with the Web interface. Springpad was bundled on new Toshiba notebook computers through a Web application subscription service. On May 23, 2014, Springpad announced that it would cease operations on June 25, 2014. The company then allowed users to export their data (as JSON and read-only HTML formats), or to automatically migrate it to Evernote accounts before the expiration date. == Features == Springpad users could use the main site interface which uses HTML5 from most browsers or use the smartphone app to capture notes, tasks, or lists which were then added to the user's "My Stuff", the user's personal database or collection. Additionally Springpad let users look up items of interest which were then automatically categorized based on type or manually categorized by the user. Category types included recipes, movies, products, restaurants and wine. Events could also be added to Springpad, and if the user used Google Calendar, they could opt to sync the event to it. In addition to the smartphone app and site, Springpad could be used via browser extension for Google Chrome, or the Springpad Clipper, a bookmarklet to analyze webpages and clip relevant information from them—for example, the ingredients needed for a recipe—or to add the site as a normal bookmark. Another way users could add content to their Springpad "My Stuff" was by emailing entries to an email address specified on Springpad registration. Springpad's smartphone apps could be used to scan barcodes to identify products, save them to the user's "My Stuff", and automatically generate additional product information and links. The mobile app could also save images taken with the phone's camera, and locate nearby businesses. With most of the content added to a user's "My Stuff", relevant news, useful links and other helpful information could be viewed. Users could also attach additional notes and images to content they had already saved, and could add reminders and alerts which could be emailed to the user or texted to their phone. Springpad also added alerts to its own Alerts section for relevant news, deals or coupons for specific products users added. For additional organization, anything added to Springpad could also be tagged. Users could also add entries to "Notebooks" to separate content by projects, or any other way they wished. Each Notebook included a section called a "Board", which acted as a pin board where users could "pin" content they'd added to the Notebook, allowing them to visually lay out items. If the user added a map to the Board and had entries that included an address, Springpad could automatically point out entries on the map. By default, everything added to Springpad was private. However users could change the privacy settings for each of the types of items added, decide to make specific items public and shareable on Facebook and Twitter, add them to their public page, or keep them private but links to them with specific people.
Deluxe Paint
Deluxe Paint, often referred to as DPaint, is a bitmap graphics editor created by Dan Silva for Electronic Arts and published for the then-new Amiga 1000 in November 1985. A series of updated versions followed, some of which were ported to other platforms. An MS-DOS release with support for the 256 color VGA standard became popular for creating pixel graphics in video games in the 1990s. Author Dan Silva previously worked on the Cut & Paste word processor (1984), also from Electronic Arts. == History == Deluxe Paint began as an in-house art development tool called Prism. As author Dan Silva added features to Prism, it was developed as a showcase product to coincide with the Amiga's debut in 1985. Upon release, it was quickly embraced by the Amiga community and became the de facto graphics (and later animation) editor for the platform. Amiga manufacturer Commodore International later commissioned EA to create version 4.5 AGA to bundle with the new Advanced Graphics Architecture chipset (A1200, A4000) capable Amigas. Version 5 was the last release after Commodore's bankruptcy in 1994. Early versions of Deluxe Paint were available in protected and non copy-protected versions, the latter retailing for a slightly higher price. The copy protection scheme was later dropped. Deluxe Paint was first in a series of products from the Electronic Arts Tools group—then later moved to the ICE (for Interactivity, Creativity, and Education) group—which included such Amiga programs as Deluxe Music Construction Set (preceded by Music Construction Set for the Apple II), Deluxe Video, and the Studio series of paint programs for the Mac. With the development of Deluxe Paint, EA introduced the ILBM and ANIM file format standards for graphics. While widely used on the Amiga, these formats never gained widespread end user acceptance on other platforms, but were heavily used by game development companies. Deluxe Paint was used by LucasArts to make graphics for their adventure games such as The Secret of Monkey Island, and the name of a particular filename used to store the main protagonist Guybrush Threepwood was probably at the origin of his peculiar name. One of the main artist developer of the game, Mark Ferrari, in an interview for The Making of Monkey Island 30th Anniversary Documentary remembers that "there was a pulldown menu in DPaint called brushes, so character sprites were referred to as brushes", and the male protagonist was simply "the guy.brush" until the artist Steve Purcell suggested to take the very name "Guybrush". The author Ron Gilbert remembers that the PC DOS version of the file was named "guybrush.bbm". == Versions == === Amiga === Deluxe Paint I was released in 1985. A major feature was animation by using color cycling. The Amiga natively supports indexed color, where a pixel's color value does not carry any RGB hue information but instead is an index to a color palette (a collection of unique color values). By adjusting the color value in the palette, all pixels with that palette value change simultaneously in the image or animation, creating cyclic movement in the image. In the Christmas demo files on the Deluxe Paint I disk, this kind of animation (which is toggled by pressing the tab key) is used to depict falling snowflakes, a blinking Christmas tree, and a roaring fire in the fireplace. In 1986, Deluxe Paint II was introduced, which added many convenient features such as pattern and gradient fill, which could be selected by right-clicking on a fill tool. An effects menu with e.g. perspective transformation was also added. The screen format could now be changed from a dedicated selection page. Deluxe Paint III appeared in 1989 and added support for Extra Halfbrite. New editing modes allowed one to stencil certain colors to protect them, so it is possible to e.g. paint a landscape from front to back, with the foreground protected by a stencil. A major new feature of Deluxe Paint III was the ability to create cel-like animation, and animbrushes (1MB of RAM is needed for animation). These let the user pick up a section of an animation as an "animbrush", which can then be placed onto the canvas while it animates. Deluxe Paint III was one of the first paint programs to support animbrushes. This is similar to copy and paste, except one can pick up more than one image. Deluxe Paint IV (introduced in 1991), which did not include Silva as the lead programmer, offered significant new features like non-bitplane-indexed Hold-and-Modify support for creating images with up to 4,096 colors. Animation support was improved by adding a light table, i.e. onion skinning, and AnimBrush morphing. The color mixer was now a HAM region at the bottom of the screen (instead of a floating window as before) and allowed mixing adjacent colors similar to a real palette. Deluxe Paint 4.5 AGA appeared the following year, addressing the stability issues and providing support for the new A1200 and A4000 AGA machines and a revamped screen mode interface. It appeared in both standalone and Commodore-bundled versions. The final release, Deluxe Paint V, in 1995, supported true 24-bit RGB images. However, using only the AGA native chipset, the 24-bit RGB color was only held in computer memory, the on-screen image was displayed in HAM8 (18-bit color). === Apple IIGS === DeluxePaint II for the Apple IIGS was developed by Brent Iverson and released in 1987. === MS-DOS === Deluxe Paint II for MS-DOS was released in 1988, It required MS-DOS 2.0 and 640 kB of RAM. It supports CGA, EGA, MCGA, VGA, Hercules and Tandy IBM PC-compatible graphic cards. Deluxe Paint II Enhanced was released in 1989, requiring MS-DOS 2.11 and 640 kB of RAM. It supports resolutions up to 800x600 pixels with 256 colors. Deluxe Paint II Enhanced 2.0, released in 1994, was the most successful MS-DOS version, and was compatible with PC Paintbrush PCX image files. The MS-DOS conversion was done by Brent Iverson with the enhanced features by Steve Shaw. It supports CGA, EGA, MCGA, VGA, Hercules, Tandy, and Amstrad video cards, as well as early Super VGA video cards enabling it to support up to 800 × 600 with 256 (from 262,144) colors and 1024 × 768 with 16 colors. The sister product Deluxe Paint Animation (only for 320×200 pixels and 256 colors) was widely used, especially in video game development. === Atari ST === Deluxe Paint ST was developed by ArtisTech Development, published by Electronic Arts, and was released in 1990. It supports the Atari STE 4096 color palette and animated graphics. Features advertised for the Atari ST version include 3D perspective, design your own fonts, mirror symmetry, multi-color airbrushing & animations, printing up to poster size, split-screen magnification with variable zoom, and working on animations (including multiple animations). == Workflow == "[" and "]" hotkeys step through the indexed palette, turning indexed-pixel-painting into a fast two-handed mouse+keys process, and the right mouse button paints with the background color. For example, transparency is obtained as simply as selecting a background color index (a single right click on the palette GUI to change). colors could be locked from editing by use of a stencil (a list of color indices whose pixels should not be altered in the image data) and simple color-cycling animations could be created using contiguous entries in the palette. This was easy to change the hue and tone of a section of the image by altering the corresponding colors in the palette. (The specific section needed to use a dedicated part of the palette for this technique to work.) Brushes can be cut from the background by using the box, freehand, or polygon selection tools. They can then be used in the same manner as any other brush or pen. This functionality is simpler to use than the "stamp" tool of Photoshop or Alpha Channels as provided in later programs. Brushes can be rotated and scaled, even in 3D. After a brush is selected, it appears attached to the mouse cursor, providing an exact preview of what will be drawn. This allows precise pixel positioning of brushes. Animations stored in IFF ANIM format are delta compressed making animations both smaller and faster to playback. == Reception == Compute! criticized the documentation of the first release of DeluxePaint as inadequate, but stated that "DeluxePaint is a visual arts program of immense scope and flexibility". In later versions the documentation was much improved; for instance DeluxePaint IV came with a 300-page manual. Deluxe Paint was a hit for EA. The main line of the series, particularly installments one to three, has won a total of at least nine awards from independent publications and organizations, including three Amiga-specific awards. Deluxe Paint III also won Commodore International's Enterprise and Vision award in 1990, becoming the first software to win the award, for what the company's judges believed to be best utilizing the Amiga's graphical capabilities. Deluxe Pai
Voiceverse NFT plagiarism scandal
In January 2022, 15—the pseudonymous Massachusetts Institute of Technology (MIT) artificial intelligence researcher and creator of the non-commercial generative artificial intelligence voice synthesis research project 15.ai—discovered that the blockchain-based technology company Voiceverse had plagiarized from their platform. Voiceverse marketed itself as a service that offered AI voice cloning technology that could be purchased and traded as non-fungible tokens (NFTs). Amid heightened controversy over NFTs in the gaming industry, voice actor Troy Baker (who has been described as one of the most famous voice actors in video games) announced his partnership with Voiceverse on January 14, 2022, triggering immediate backlash over concerns about the environmental impact of NFTs, potential for fraud, predatory monetization in video games, and the potential of AI displacing jobs for human voice actors. Later that same day, 15 revealed through server logs that Voiceverse had generated voice lines using 15's free text-to-speech platform, pitch-shifted the audio to make them unrecognizable, and falsely marketed the samples as their own technology before selling them as NFTs. Within an hour of being confronted with evidence, Voiceverse confessed and stated that their marketing team had used 15.ai without proper attribution while rushing to create a technology demo to coincide with Baker's partnership announcement, further exacerbating the already negative reception to the original announcement. In response, 15 replied "Go fuck yourself"; the interaction went viral and garnered a large amount of support for the developer. News publications universally characterized this incident as Voiceverse having "stolen" from 15.ai. The next day, Baker appeared on a podcast and stated that his motivation had been to help independent creators who were unable to afford professional voice actors. Following continued backlash and the plagiarism revelation, Baker ended his partnership with Voiceverse on January 31, 2022. Subsequently, the incident was documented in multiple AI ethics databases, criticisms of predatory monetization in video games, and retrospectives as one of the earliest instances of plagiarism and theft stemming from artificial intelligence during the AI boom. == Background == === Troy Baker === Troy Baker is a prominent voice actor in the video game industry best known for his performances as Joel Miller in The Last of Us franchise. Baker has been described as "ubiquitous" by Polygon, "one of the most high-profile and prolific voice actors in video games" by Eurogamer, and "arguably the most famous voice actor in the gaming industry" by GameGuru. His other prominent roles include voicing Agent John "Jonesy" Jones in Fortnite, Booker DeWitt in BioShock Infinite, and both Batman and Joker in multiple Batman video games. As of October 2025, Baker holds the record for the most acting nominations at the BAFTA Games Awards, with five between 2013 and 2021. === Voiceverse === Voiceverse is a blockchain-based startup founded by the Bored Ape Yacht Club that marketed itself as offering AI voice cloning technology in the form of NFTs. Prior to the announcement of their partnership with Baker, Voiceverse had partnered with LOVO, Inc., an AI voice platform that, according to LOVO, could generate human-like voices. Voiceverse stated that any user who purchases a voice NFT would have unlimited and perpetual access to the voice model, which could be used to create content such as audiobooks, YouTube videos, podcasts, e-learning materials, in-game voice chat, and Zoom calls. Voiceverse promised that buyers would "OWN [sic] all of the IP" of content they created using these voices. Voiceverse's roadmap included plans to release 8,888 initial voice NFTs, a feature to add emotions to existing voices, and the ability for users to mint their own voices as NFTs. Prior to Baker's partnership, Voiceverse had also partnered with voice actors Charlet Chung, who voices D.Va in Overwatch, and Andy Milonakis of The Andy Milonakis Show. === 15.ai === 15.ai is a free web application launched in 2020 that uses artificial intelligence to generate text-to-speech voices of fictional characters from popular media. Created by a pseudonymous artificial intelligence researcher known as 15, who began developing the technology as a freshman during their undergraduate research at MIT, it was an early example of an application of generative artificial intelligence during the initial stages of the AI boom. The platform showed that deep neural networks could generate emotionally expressive speech with only 15 seconds of speech; the name "15.ai" references the creator's statement that a voice can be convincingly cloned with just 15 seconds of audio, as opposed to the tens of hours of data previously required. 15.ai became an Internet phenomenon in early 2021 when content utilizing it went viral on social media and quickly gained widespread use among various Internet fandoms. 15 has emphasized that it remain free and non-commercial; it only requires users to give proper credit when using the service for content creation. === NFTs in the video game industry === By early 2022, NFTs had become highly controversial within the gaming industry. Critics raised concerns about their environmental impact due to the significant energy consumption of blockchain technology. In addition, the prevalence of scams, fraud, and potential money laundering associated with NFT sales, as well as fears that NFTs were a new form of predatory monetization following the increasing frequency of loot boxes, caused vocal pushback from the gaming community. Several major gaming companies had begun exploring NFT integration into their products, though fan backlash had already forced some projects to be cancelled. On December 16, 2021, the developers of S.T.A.L.K.E.R. 2: Heart of Chernobyl announced that they would be including NFTs in the game, but cancelled within an hour of the announcement due to immediate universal backlash. Simultaneously, the rise of AI voice technology raised concerns among voice actors about potential job displacement and the devaluation of their work amidst the voice acting industry's ongoing struggles for better compensation and working conditions. == Partnership announcement and backlash == On January 14, 2022, 1:02 a.m. EST, Baker announced on Twitter that he was partnering with Voiceverse "to explore ways where together we might bring new tools to new creators to make new things, and allow everyone a chance to own & invest in the IP's they create." The announcement concluded with the statement "You can hate. Or you can create." Baker's specific role with Voiceverse remained unclear at the time of the announcement. Along with Baker's announcement, Voiceverse promoted their supposed voice AI technology on Twitter by posting animated videos that featured a cat character created by NFT firm Chubbiverse. The videos concluded with text that read "The Voice Powered By Voiceverse"; Voiceverse stated on Twitter that the voices in the animations had been generated using their own AI voice synthesis technology and presented the videos as a technology demonstration of their voice NFT capabilities. The announcement provoked immediate and widespread backlash from the gaming community. Baker's tweet received thousands of replies and quote retweets (the vast majority of which were negative), far more than the number of likes; Michael McWhertor of Polygon described it as a "textbook example of being ratioed" and commented that reactions had been amplified by the final part of Baker's announcement. Michael Beckwith of Metro called Baker's approach "bizarrely aggressive". Later that day, Baker responded to the backlash by apologizing for his choice of words. He said he appreciated people's thoughts and acknowledged that the "hate/create part might have been a bit antagonistic," calling it a "bad attempt to bring levity". Despite the apology, Baker and his fellow voice actors did not distance themselves from Voiceverse at this point. At the same time, Voiceverse attempted to address the criticisms, stating that they were working to move to more environmentally friendly blockchain technology and that voice actors would receive royalties from NFT sales, with actors benefiting from any increase in NFT value. == Plagiarism revelation == On December 13, 2021, amidst the increasingly negative reactions toward NFTs among the general public, the creator of 15.ai (known pseudonymously as 15) announced that they had "no interest in incorporating NFTs into any aspect of [their] work." On January 14, 2022, 11:17 a.m. EST (10 hours after Baker's initial announcement), 15 commented on the Voiceverse venture, stating that it "sounds like a scam". Two hours later, at 1:20 p.m., 15 explicitly accused Voiceverse of "actively attempting to appropriate [15's] work for [Voiceverse's] own benefit." 15 provided evidence through
Rendezvous hashing
Rendezvous or highest random weight (HRW) hashing is an algorithm that allows clients to achieve distributed agreement on a set of k {\displaystyle k} options out of a possible set of n {\displaystyle n} options. A typical application is when clients need to agree on which sites (or proxies) objects are assigned to. Consistent hashing addresses the special case k = 1 {\displaystyle k=1} using a different method. Rendezvous hashing is both much simpler and more general than consistent hashing (see below). == History == Rendezvous hashing was invented by David Thaler and Chinya Ravishankar at the University of Michigan in 1996. Consistent hashing appeared a year later in the literature. Given its simplicity and generality, rendezvous hashing is now being preferred to consistent hashing in real-world applications. Rendezvous hashing was used very early on in many applications including mobile caching, router design, secure key establishment, and sharding and distributed databases. Other examples of real-world systems that use Rendezvous Hashing include the GitHub load balancer, the Apache Ignite distributed database, the Tahoe-LAFS file store, the CoBlitz large-file distribution service, Apache Druid, IBM's Cloud Object Store, the Arvados Data Management System, Apache Kafka, and the Twitter EventBus pub/sub platform. One of the first applications of rendezvous hashing was to enable multicast clients on the Internet (in contexts such as the MBONE) to identify multicast rendezvous points in a distributed fashion. It was used in 1998 by Microsoft's Cache Array Routing Protocol (CARP) for distributed cache coordination and routing. Some Protocol Independent Multicast routing protocols use rendezvous hashing to pick a rendezvous point. == Problem definition and approach == === Algorithm === Rendezvous hashing solves a general version of the distributed hash table problem: We are given a set of n {\displaystyle n} sites (servers or proxies, say). How can any set of clients, given an object O {\displaystyle O} , agree on a k-subset of sites to assign to O {\displaystyle O} ? The standard version of the problem uses k = 1. Each client is to make its selection independently, but all clients must end up picking the same subset of sites. This is non-trivial if we add a minimal disruption constraint, and require that when a site fails or is removed, only objects mapping to that site need be reassigned to other sites. The basic idea is to give each site S j {\displaystyle S_{j}} a score (a weight) for each object O i {\displaystyle O_{i}} , and assign the object to the highest scoring site. All clients first agree on a hash function h ( ⋅ ) {\displaystyle h(\cdot )} . For object O i {\displaystyle O_{i}} , the site S j {\displaystyle S_{j}} is defined to have weight w i , j = h ( O i , S j ) {\displaystyle w_{i,j}=h(O_{i},S_{j})} . Each client independently computes these weights w i , 1 , w i , 2 … w i , n {\displaystyle w_{i,1},w_{i,2}\dots w_{i,n}} and picks the k sites that yield the k largest hash values. The clients have thereby achieved distributed k {\displaystyle k} -agreement. If a site S {\displaystyle S} is added or removed, only the objects mapping to S {\displaystyle S} are remapped to different sites, satisfying the minimal disruption constraint above. The HRW assignment can be computed independently by any client, since it depends only on the identifiers for the set of sites S 1 , S 2 … S n {\displaystyle S_{1},S_{2}\dots S_{n}} and the object being assigned. HRW easily accommodates different capacities among sites. If site S k {\displaystyle S_{k}} has twice the capacity of the other sites, we simply represent S k {\displaystyle S_{k}} twice in the list, say, as S k , 1 , S k , 2 {\displaystyle S_{k,1},S_{k,2}} . Clearly, twice as many objects will now map to S k {\displaystyle S_{k}} as to the other sites. === Properties === Consider the simple version of the problem, with k = 1, where all clients are to agree on a single site for an object O. Approaching the problem naively, it might appear sufficient to treat the n sites as buckets in a hash table and hash the object name O into this table. Unfortunately, if any of the sites fails or is unreachable, the hash table size changes, forcing all objects to be remapped. This massive disruption makes such direct hashing unworkable. Under rendezvous hashing, however, clients handle site failures by picking the site that yields the next largest weight. Remapping is required only for objects currently mapped to the failed site, and disruption is minimal. Rendezvous hashing has the following properties: Low overhead: The hash function used is efficient, so overhead at the clients is very low. Load balancing: Since the hash function is randomizing, each of the n sites is equally likely to receive the object O. Loads are uniform across the sites. Site capacity: Sites with different capacities can be represented in the site list with multiplicity in proportion to capacity. A site with twice the capacity of the other sites will be represented twice in the list, while every other site is represented once. High hit rate: Since all clients agree on placing an object O into the same site SO, each fetch or placement of O into SO yields the maximum utility in terms of hit rate. The object O will always be found unless it is evicted by some replacement algorithm at SO. Minimal disruption: When a site fails, only the objects mapped to that site need to be remapped. Disruption is at the minimal possible level. Distributed k-agreement: Clients can reach distributed agreement on k sites simply by selecting the top k sites in the ordering. == O(log n) running time via skeleton-based hierarchical rendezvous hashing == The standard version of Rendezvous Hashing described above works quite well for moderate n, but when n {\displaystyle n} is extremely large, the hierarchical use of Rendezvous Hashing achieves O ( log n ) {\displaystyle O(\log n)} running time. This approach creates a virtual hierarchical structure (called a "skeleton"), and achieves O ( log n ) {\displaystyle O(\log n)} running time by applying HRW at each level while descending the hierarchy. The idea is to first choose some constant m {\displaystyle m} and organize the n {\displaystyle n} sites into c = ⌈ n / m ⌉ {\displaystyle c=\lceil n/m\rceil } clusters C 1 = { S 1 , S 2 … S m } , C 2 = { S m + 1 , S m + 2 … S 2 m } … {\displaystyle C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots } Next, build a virtual hierarchy by choosing a constant f {\displaystyle f} and imagining these c {\displaystyle c} clusters placed at the leaves of a tree T {\displaystyle T} of virtual nodes, each with fanout f {\displaystyle f} . In the accompanying diagram, the cluster size is m = 4 {\displaystyle m=4} , and the skeleton fanout is f = 3 {\displaystyle f=3} . Assuming 108 sites (real nodes) for convenience, we get a three-tier virtual hierarchy. Since f = 3 {\displaystyle f=3} , each virtual node has a natural numbering in octal. Thus, the 27 virtual nodes at the lowest tier would be numbered 000 , 001 , 002 , . . . , 221 , 222 {\displaystyle 000,001,002,...,221,222} in octal (we can, of course, vary the fanout at each level - in that case, each node will be identified with the corresponding mixed-radix number). The easiest way to understand the virtual hierarchy is by starting at the top, and descending the virtual hierarchy. We successively apply Rendezvous Hashing to the set of virtual nodes at each level of the hierarchy, and descend the branch defined by the winning virtual node. We can in fact start at any level in the virtual hierarchy. Starting lower in the hierarchy requires more hashes, but may improve load distribution in the case of failures. For example, instead of applying HRW to all 108 real nodes in the diagram, we can first apply HRW to the 27 lowest-tier virtual nodes, selecting one. We then apply HRW to the four real nodes in its cluster, and choose the winning site. We only need 27 + 4 = 31 {\displaystyle 27+4=31} hashes, rather than 108. If we apply this method starting one level higher in the hierarchy, we would need 9 + 3 + 4 = 16 {\displaystyle 9+3+4=16} hashes to get to the winning site. The figure shows how, if we proceed starting from the root of the skeleton, we may successively choose the virtual nodes ( 2 ) 3 {\displaystyle (2)_{3}} , ( 20 ) 3 {\displaystyle (20)_{3}} , and ( 200 ) 3 {\displaystyle (200)_{3}} , and finally end up with site 74. The virtual hierarchy need not be stored, but can be created on demand, since the virtual nodes names are simply prefixes of base- f {\displaystyle f} (or mixed-radix) representations. We can easily create appropriately sorted strings from the digits, as required. In the example, we would be working with the strings 0 , 1 , 2 {\displaystyle 0,1,2} (at tier 1), 20 , 21 , 22 {\displaystyle 20,21,22} (at tier 2), and 200 , 201 , 202
Kleene's algorithm
In theoretical computer science, in particular in formal language theory, Kleene's algorithm transforms a given nondeterministic finite automaton (NFA) into a regular expression. Together with other conversion algorithms, it establishes the equivalence of several description formats for regular languages. Alternative presentations of the same method include the "elimination method" attributed to Brzozowski and McCluskey, the algorithm of McNaughton and Yamada, and the use of Arden's lemma. == Algorithm description == According to Gross and Yellen (2004), the algorithm can be traced back to Kleene (1956). A presentation of the algorithm in the case of deterministic finite automata (DFAs) is given in Hopcroft and Ullman (1979). The presentation of the algorithm for NFAs below follows Gross and Yellen (2004). Given a nondeterministic finite automaton M = (Q, Σ, δ, q0, F), with Q = { q0,...,qn } its set of states, the algorithm computes the sets Rkij of all strings that take M from state qi to qj without going through any state numbered higher than k. Here, "going through a state" means entering and leaving it, so both i and j may be higher than k, but no intermediate state may. Each set Rkij is represented by a regular expression; the algorithm computes them step by step for k = -1, 0, ..., n. Since there is no state numbered higher than n, the regular expression Rn0j represents the set of all strings that take M from its start state q0 to qj. If F = { q1,...,qf } is the set of accept states, the regular expression Rn01 | ... | Rn0f represents the language accepted by M. The initial regular expressions, for k = -1, are computed as follows for i≠j: R−1ij = a1 | ... | am where qj ∈ δ(qi,a1), ..., qj ∈ δ(qi,am) and as follows for i=j: R−1ii = a1 | ... | am | ε where qi ∈ δ(qi,a1), ..., qi ∈ δ(qi,am) In other words, R−1ij mentions all letters that label a transition from i to j, and we also include ε in the case where i=j. After that, in each step the expressions Rkij are computed from the previous ones by Rkij = Rk-1ik (Rk-1kk) Rk-1kj | Rk-1ij Another way to understand the operation of the algorithm is as an "elimination method", where the states from 0 to n are successively removed: when state k is removed, the regular expression Rk-1ij, which describes the words that label a path from state i>k to state j>k, is rewritten into Rkij so as to take into account the possibility of going via the "eliminated" state k. By induction on k, it can be shown that the length of each expression Rkij is at most 1/3(4k+1(6s+7) - 4) symbols, where s denotes the number of characters in Σ. Therefore, the length of the regular expression representing the language accepted by M is at most 1/3(4n+1(6s+7)f - f - 3) symbols, where f denotes the number of final states. This exponential blowup is inevitable, because there exist families of DFAs for which any equivalent regular expression must be of exponential size. In practice, the size of the regular expression obtained by running the algorithm can be very different depending on the order in which the states are considered by the procedure, i.e., the order in which they are numbered from 0 to n. == Example == The automaton shown in the picture can be described as M = (Q, Σ, δ, q0, F) with the set of states Q = { q0, q1, q2 }, the input alphabet Σ = { a, b }, the transition function δ with δ(q0,a)=q0, δ(q0,b)=q1, δ(q1,a)=q2, δ(q1,b)=q1, δ(q2,a)=q1, and δ(q2,b)=q1, the start state q0, and set of accept states F = { q1 }. Kleene's algorithm computes the initial regular expressions as After that, the Rkij are computed from the Rk-1ij step by step for k = 0, 1, 2. Kleene algebra equalities are used to simplify the regular expressions as much as possible. Step 0 Step 1 Step 2 Since q0 is the start state and q1 is the only accept state, the regular expression R201 denotes the set of all strings accepted by the automaton.
Language resource
In linguistics and language technology, a language resource is a "[composition] of linguistic material used in the construction, improvement and/or evaluation of language processing applications, (...) in language and language-mediated research studies and applications." According to Bird & Simons (2003), this includes data, i.e. "any information that documents or describes a language, such as a published monograph, a computer data file, or even a shoebox full of handwritten index cards. The information could range in content from unanalyzed sound recordings to fully transcribed and annotated texts to a complete descriptive grammar", tools, i.e., "computational resources that facilitate creating, viewing, querying, or otherwise using language data", and advice, i.e., "any information about what data sources are reliable, what tools are appropriate in a given situation, what practices to follow when creating new data". The latter aspect is usually referred to as "best practices" or "(community) standards". In a narrower sense, language resource is specifically applied to resources that are available in digital form, and then, "encompassing (a) data sets (textual, multimodal/multimedia and lexical data, grammars, language models, etc.) in machine readable form, and (b) tools/technologies/services used for their processing and management". == Typology == As of May 2020, no widely used standard typology of language resources has been established (current proposals include the LREMap, METASHARE, and, for data, the LLOD classification). Important classes of language resources include data lexical resources, e.g., machine-readable dictionaries, linguistic corpora, i.e., digital collections of natural language data, linguistic data bases such as the Cross-Linguistic Linked Data collection, tools linguistic annotations and tools for creating such annotations in a manual or semiautomated fashion (e.g., tools for annotating interlinear glossed text such as Toolbox and FLEx, or other language documentation tools), applications for search and retrieval over such data (corpus management systems), for automated annotation (part-of-speech tagging, syntactic parsing, semantic parsing, etc.), metadata and vocabularies vocabularies, repositories of linguistic terminology and language metadata, e.g., MetaShare (for language resource metadata), the ISO 12620 data category registry (for linguistic features, data structures and annotations within a language resource), or the Glottolog database (identifiers for language varieties and bibliographical database). == Language resource publication, dissemination and creation == A major concern of the language resource community has been to develop infrastructures and platforms to present, discuss and disseminate language resources. Selected contributions in this regard include: a series of International Conferences on Language Resources and Evaluation (LREC), the European Language Resources Association (ELRA, EU-based), and the Linguistic Data Consortium (LDC, US-based), which represent commercial hosting and dissemination platforms for language resources, the Open Languages Archives Community (OLAC), which provides and aggregates language resource metadata, the Language Resources and Evaluation Journal (LREJ), the European Language Grid is a European platform for language technologies (eg services), data and resources. As for the development of standards and best practices for language resources, these are subject of several community groups and standardization efforts, including ISO Technical Committee 37: Terminology and other language and content resources (ISO/TC 37), developing standards for all aspects of language resources, W3C Community Group Best Practices for Multilingual Linked Open Data (BPMLOD), working on best practice recommendations for publishing language resources as Linked Data or in RDF, W3C Community Group Linked Data for Language Technology (LD4LT), working on linguistic annotations on the web and language resource metadata, W3C Community Group Ontology-Lexica (OntoLex), working on lexical resources, the Open Linguistics working group of the Open Knowledge Foundation, working on conventions for publishing and linking open language resources, developing the Linguistic Linked Open Data cloud, the Text Encoding Initiative (TEI), working on XML-based specifications for language resources and digitally edited text.
Time Warp Edit Distance
In the data analysis of time series, Time Warp Edit Distance (TWED) is a measure of similarity (or dissimilarity) between pairs of discrete time series, controlling the relative distortion of the time units of the two series using the physical notion of elasticity. In comparison to other distance measures, (e.g. DTW (dynamic time warping) or LCS (longest common subsequence problem)), TWED is a metric. Its computational time complexity is O ( n 2 ) {\displaystyle O(n^{2})} , but can be drastically reduced in some specific situations by using a corridor to reduce the search space. Its memory space complexity can be reduced to O ( n ) {\displaystyle O(n)} . It was first proposed in 2009 by P.-F. Marteau. == Definition == δ λ , ν ( A 1 p , B 1 q ) = M i n { δ λ , ν ( A 1 p − 1 , B 1 q ) + Γ ( a p ′ → Λ ) d e l e t e i n A δ λ , ν ( A 1 p − 1 , B 1 q − 1 ) + Γ ( a p ′ → b q ′ ) m a t c h o r s u b s t i t u t i o n δ λ , ν ( A 1 p , B 1 q − 1 ) + Γ ( Λ → b q ′ ) d e l e t e i n B {\displaystyle \delta _{\lambda ,\nu }(A_{1}^{p},B_{1}^{q})=Min{\begin{cases}\delta _{\lambda ,\nu }(A_{1}^{p-1},B_{1}^{q})+\Gamma (a_{p}^{'}\to \Lambda )&{\rm {delete\ in\ A}}\\\delta _{\lambda ,\nu }(A_{1}^{p-1},B_{1}^{q-1})+\Gamma (a_{p}^{'}\to b_{q}^{'})&{\rm {match\ or\ substitution}}\\\delta _{\lambda ,\nu }(A_{1}^{p},B_{1}^{q-1})+\Gamma (\Lambda \to b_{q}^{'})&{\rm {delete\ in\ B}}\end{cases}}} whereas Γ ( α p ′ → Λ ) = d L P ( a p ′ , a p − 1 ′ ) + ν ⋅ ( t a p − t a p − 1 ) + λ {\displaystyle \Gamma (\alpha _{p}^{'}\to \Lambda )=d_{LP}(a_{p}^{'},a_{p-1}^{'})+\nu \cdot (t_{a_{p}}-t_{a_{p-1}})+\lambda } Γ ( α p ′ → b q ′ ) = d L P ( a p ′ , b q ′ ) + d L P ( a p − 1 ′ , b q − 1 ′ ) + ν ⋅ ( | t a p − t b q | + | t a p − 1 − t b q − 1 | ) {\displaystyle \Gamma (\alpha _{p}^{'}\to b_{q}^{'})=d_{LP}(a_{p}^{'},b_{q}^{'})+d_{LP}(a_{p-1}^{'},b_{q-1}^{'})+\nu \cdot (|t_{a_{p}}-t_{b_{q}}|+|t_{a_{p-1}}-t_{b_{q-1}}|)} Γ ( Λ → b q ′ ) = d L P ( b p ′ , b p − 1 ′ ) + ν ⋅ ( t b q − t b q − 1 ) + λ {\displaystyle \Gamma (\Lambda \to b_{q}^{'})=d_{LP}(b_{p}^{'},b_{p-1}^{'})+\nu \cdot (t_{b_{q}}-t_{b_{q-1}})+\lambda } Whereas the recursion δ λ , ν {\displaystyle \delta _{\lambda ,\nu }} is initialized as: δ λ , ν ( A 1 0 , B 1 0 ) = 0 , {\displaystyle \delta _{\lambda ,\nu }(A_{1}^{0},B_{1}^{0})=0,} δ λ , ν ( A 1 0 , B 1 j ) = ∞ f o r j ≥ 1 {\displaystyle \delta _{\lambda ,\nu }(A_{1}^{0},B_{1}^{j})=\infty \ {\rm {{for\ }j\geq 1}}} δ λ , ν ( A 1 i , B 1 0 ) = ∞ f o r i ≥ 1 {\displaystyle \delta _{\lambda ,\nu }(A_{1}^{i},B_{1}^{0})=\infty \ {\rm {{for\ }i\geq 1}}} with a 0 ′ = b 0 ′ = 0 {\displaystyle a'_{0}=b'_{0}=0} === Implementations === An implementation of the TWED algorithm in C with a Python wrapper is available at TWED is also implemented into the Time Series Subsequence Search Python package (TSSEARCH for short) available at [1]. An R implementation of TWED has been integrated into the TraMineR, a R package for mining, describing and visualizing sequences of states or events, and more generally discrete sequence data. Additionally, cuTWED is a CUDA- accelerated implementation of TWED which uses an improved algorithm due to G. Wright (2020). This method is linear in memory and massively parallelized. cuTWED is written in CUDA C/C++, comes with Python bindings, and also includes Python bindings for Marteau's reference C implementation. ==== Python ==== Backtracking, to find the most cost-efficient path: ==== MATLAB ==== Backtracking, to find the most cost-efficient path: