In computer science, Thompson's construction algorithm, also called the McNaughton–Yamada–Thompson algorithm, is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to match strings against the regular expression. This algorithm is credited to Ken Thompson. Regular expressions and nondeterministic finite automata are two representations of formal languages. For instance, text processing utilities use regular expressions to describe advanced search patterns, but NFAs are better suited for execution on a computer. Hence, this algorithm is of practical interest, since it can compile regular expressions into NFAs. From a theoretical point of view, this algorithm is a part of the proof that they both accept exactly the same languages, that is, the regular languages. An NFA can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression. However, an NFA may also be interpreted directly. To decide whether two given regular expressions describe the same language, each can be converted into an equivalent minimal deterministic finite automaton via Thompson's construction, powerset construction, and DFA minimization. If, and only if, the resulting automata agree up to renaming of states, the regular expressions' languages agree. == The algorithm == The algorithm works recursively by splitting an expression into its constituent subexpressions, from which the NFA will be constructed using a set of rules. More precisely, from a regular expression E, the obtained automaton A with the transition function Δ respects the following properties: A has exactly one initial state q0, which is not accessible from any other state. That is, for any state q and any letter a, Δ ( q , a ) {\displaystyle \Delta (q,a)} does not contain q0. A has exactly one final state qf, which is not co-accessible from any other state. That is, for any letter a, Δ ( q f , a ) = ∅ {\displaystyle \Delta (q_{f},a)=\emptyset } . Let c be the number of concatenation of the regular expression E and let s be the number of symbols apart from parentheses — that is, |, , a and ε. Then, the number of states of A is 2s − c (linear in the size of E). The number of transitions leaving any state is at most two. Since an NFA of m states and at most e transitions from each state can match a string of length n in time O(emn), a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet. === Rules === The following rules are depicted according to Aho et al. (2007), p. 122. In what follows, N(s) and N(t) are the NFA of the subexpressions s and t, respectively. The empty-expression ε is converted to A symbol a of the input alphabet is converted to The union expression s|t is converted to State q goes via ε either to the initial state of N(s) or N(t). Their final states become intermediate states of the whole NFA and merge via two ε-transitions into the final state of the NFA. The concatenation expression st is converted to The initial state of N(s) is the initial state of the whole NFA. The final state of N(s) becomes the initial state of N(t). The final state of N(t) is the final state of the whole NFA. The Kleene star expression s is converted to An ε-transition connects initial and final state of the NFA with the sub-NFA N(s) in between. Another ε-transition from the inner final to the inner initial state of N(s) allows for repetition of expression s according to the star operator. The parenthesized expression (s) is converted to N(s) itself. With these rules, using the empty expression and symbol rules as base cases, it is possible to prove with structural induction that any regular expression may be converted into an equivalent NFA. == Example == Two examples are now given, a small informal one with the result, and a bigger with a step by step application of the algorithm. === Small Example === The picture below shows the result of Thompson's construction on (ε|ab). The purple oval corresponds to a, the teal oval corresponds to a, the green oval corresponds to b, the orange oval corresponds to ab, and the blue oval corresponds to ε. === Application of the algorithm === As an example, the picture shows the result of Thompson's construction algorithm on the regular expression (0|(1(01(00)0)1)) that denotes the set of binary numbers that are multiples of 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }. The upper right part shows the logical structure (syntax tree) of the expression, with "." denoting concatenation (assumed to have variable arity); subexpressions are named a-q for reference purposes. The left part shows the nondeterministic finite automaton resulting from Thompson's algorithm, with the entry and exit state of each subexpression colored in magenta and cyan, respectively. An ε as transition label is omitted for clarity — unlabelled transitions are in fact ε transitions. The entry and exit state corresponding to the root expression q is the start and accept state of the automaton, respectively. The algorithm's steps are as follows: An equivalent minimal deterministic automaton is shown below. == Relation to other algorithms == Thompson's is one of several algorithms for constructing NFAs from regular expressions; an earlier algorithm was given by McNaughton and Yamada. Converse to Thompson's construction, Kleene's algorithm transforms a finite automaton into a regular expression. Glushkov's construction algorithm is similar to Thompson's construction, once the ε-transitions are removed. == Use in string pattern matching == Regular expressions are often used to specify patterns that software is then asked to match. Generating an NFA by Thompson's construction, and using an appropriate algorithm to simulate it, it is possible to create pattern-matching software with performance that is O ( m n ) {\displaystyle O(mn)} , where m is the length of the regular expression and n is the length of the string being matched. This is much better than is achieved by many popular programming-language implementations; however, it is restricted to purely regular expressions and does not support patterns for non-regular languages like backreferences.
World Database of Happiness
The World Database of Happiness is a web-based archive of research findings on subjective appreciation of life, based in the Erasmus Happiness Economics Research Organization of the Erasmus University Rotterdam in The Netherlands. The database contains both an overview of scientific publications on happiness and a digest of research findings. Happiness is defined as the degree to which an individual judges the quality of his or her life as a whole favorably. Two 'components' of happiness are distinguished: hedonic level of affect (the degree to which pleasant affect dominates) and contentment (perceived realization of wants). == Aims == The World Database of Happiness is a tool to quickly acquire an overview on the ever-growing stream of research findings on happiness Medio 2023 the database covered some 16,000 scientific publications on happiness, from which were extracted 23,000 distributional findings (on how happy people are) and another 24,000 correlational findings (on factors associated with more and less happiness). The first findings date from 1915. == Technique == The World Database of Happiness is a ‘findings archive’, which consists of electronic ‘finding pages’ on which separate research results are described in a standard format and terminology. These finding pages can be selected on various characteristics, such as population studies, the measure of happiness used and observed co-variates. All finding-pages have a specific internet address to which links can be made in scientific review papers or policy recommendations. This allows a concise presentation of many findings in a table, while providing readers with access to detail. == Scientific use == The Database has been cited in 254 scientific papers, for example to access under what conditions economic growth enhances average happiness or to show that rising mean happiness at first raises happiness inequality, but further rise will diminish these differences, or that healthy eating is associated with more happiness, even after controlling for the effect on health Another finding is that relative simple happiness training techniques raise happiness by some 5% == Popular use == The World Database of Happiness is often used by popular media to make lists of the happiest countries around the globe. An example is the Happy Planet Index, which aims to chart sustainable happiness all over the world by combining data on longevity, happiness and the size of the ecological footprint of citizens. == Strengths and weaknesses == The database has a clear conceptual focus, it includes only research findings on subjective enjoyment of one's life as a whole. Thereby it evades the Babel that has haunted the study of happiness for ages. The other side of that coin is that much interesting research is left out. The findings are reported with technical details about measurement and statistical analysis. This detail is welcomed by scholars, but makes the information difficult to digest for lay-persons. Still another limitation is that the determinants of happiness appear to vary considerably across persons and situations, which make it hard to draw general conclusions about the causes of happiness. What is clear is that poor health, separation, unemployment and lack of social contact are all strongly negatively associated with happiness. Another problem for the World database of happiness is that the studies on happiness increase with such a high rate that it gets increasingly difficult to offer a complete overview of all research findings. A further concern is that the Database of Happiness is exclusively focused on hedonic happiness (feeling good) and not on mature happiness that might exist in the face of suffering
AI Now Institute
The AI Now Institute (AI Now) is an American research institute studying the social implications of artificial intelligence and policy research that addresses the concentration of power in the tech industry. AI Now has partnered with organizations such as the Distributed AI Research Institute (DAIR), Data & Society, Ada Lovelace Institute, New York University Tandon School of Engineering, New York University Center for Data Science, Partnership on AI, and the ACLU. AI Now has produced annual reports that examine the social implications of artificial intelligence. In 2021–22, AI Now's leadership served as a Senior Advisors on AI to Chair Lina Khan at the Federal Trade Commission. Its executive director is Amba Kak. == Founding and mission == AI Now grew out of a 2016 symposium organized by Obama's White House Office of Science and Technology Policy. The event was led by Meredith Whittaker, the founder of Google's Open Research Group, and Kate Crawford, a principal researcher at Microsoft Research. The event focused on near-term implications of AI in social domains: Inequality, Labor, Ethics, and Healthcare. In November 2017, AI Now held a second symposium on AI and social issues, and publicly launched the AI Now Institute in partnership with New York University. It is claimed to be the first university research institute focused on the social implications of AI, and the first AI institute founded and led by women. It is now a fully independent institute. In an interview with NPR, Crawford stated that the motivation for founding AI Now was that the application of AI into social domains - such as health care, education, and criminal justice - was being treated as a purely technical problem. The goal of AI Now's research is to treat these as social problems first, and bring in domain experts in areas like sociology, law, and history to study the implications of AI. == Research == AI Now publishes an annual report on the state of AI and its integration into society. Its 2017 report stated that "current framings of AI ethics are failing" and provided ten strategic recommendations for the field - including pre-release trials of AI systems, and increased research into bias and diversity in the field. The report was noted for calling for an end to "black box" systems in core social domains, such as those responsible for criminal justice, healthcare, welfare, and education. In April 2018, AI Now released a framework for algorithmic impact assessments, as a way for governments to assess the use of AI in public agencies. According to AI Now, an AIA would be similar to environmental impact assessment, in that it would require public disclosure and access for external experts to evaluate the effects of an AI system, and any unintended consequences. This would allow systems to be vetted for issues like biased outcomes or skewed training data, which researchers have already identified in algorithmic systems deployed across the country. Its 2023 Report argued that meaningful reform of the tech sector must focus on addressing concentrated power in the tech industry.
Blocks world
The blocks world is a planning domain in artificial intelligence. It consists of a set of wooden blocks of various shapes and colors sitting on a table. The goal is to build one or more vertical stacks of blocks. Only one block may be moved at a time: it may either be placed on the table or placed atop another block. Because of this, any blocks that are, at a given time, under another block cannot be moved. Moreover, some kinds of blocks cannot have other blocks stacked on top of them. The simplicity of this toy world lends itself readily to classical symbolic artificial intelligence approaches, in which the world is modeled as a set of abstract symbols which may be reasoned about. == Motivation == Artificial Intelligence can be researched in theory and with practical applications. The problem with most practical applications is that the engineers don't know how to program an AI system. Instead of rejecting the challenge at all the idea is to invent an easy to solve domain which is called a toy problem. Toy problems were invented with the aim to program an AI which can solve it. The blocks world domain is an example of a toy problem. Its major advantage over more realistic AI applications is that many algorithms and software programs are available which can handle the situation. This allows comparing different theories against each other. In its basic form, the blocks world problem consists of cubes of the same size which have all the color black. A mechanical robot arm has to pick and place the cubes. More complicated derivatives of the problem consist of cubes of different sizes, shapes and colors. From an algorithmic perspective, blocks world is an NP-hard search and planning problem. The task is to bring the system from an initial state into a goal state. Automated planning and scheduling problems are usually described in the Planning Domain Definition Language (PDDL) notation which is an AI planning language for symbolic manipulation tasks. If something was formulated in the PDDL notation, it is called a domain. Therefore, the task of stacking blocks is a blocks world domain which stands in contrast to other planning problems like the dock worker robot domain and the monkey and banana problem. == Theses/projects which took place in a blocks world == Terry Winograd's SHRDLU Patrick Winston's Learning Structural Descriptions from Examples and Copy Demo Gerald Jay Sussman's Sussman anomaly Decision problem (Gupta and Nau, 1992): Given a starting Blocks World, an ending Blocks World, and an integer L > 0, is there a way to move the blocks to change the starting position to the ending position with L or less steps? This decision problem is NP-hard.
Cube 3D
Cube 3D is an artificial intelligence model that is developed by Roblox Corporation. It is open source and available on GitHub and Hugging Face. In March 2026, Roblox announced Cube 3D as a mesh generation model that takes text input. In February 2026, Roblox released 4D creation in a public beta, allowing embedding Cube 3D into Roblox games. Cube 3D is integrated into Roblox Studio and its API, and supports two modes of 4D creation. == History == In March 2025, Roblox announced Cube 3D as a mesh generation model that takes text input. Its first feature was an API that allows mesh generation. That month, it was made open source. Over 1.8 million assets have been generated by Cube 3D since March 2025. In March 2025, 4D creation was announced. That November, 4D creation was released in early access. In February 2026, Roblox released 4D creation in a public beta, allowing embedding Cube 3D into Roblox games. == Technology == Cube 3D is trained on Roblox meshes. To generate meshes, it tokenises meshes and shapes and predicts the next token. Cube 3D is integrated into Roblox Studio and the Roblox Studio API. Its API allows mesh generation. In 4D creation, two modes can be used. Car-5 supports modular objects, and Body-1 only supports single-mesh objects.
CodeSandbox
CodeSandbox is a cloud-based online integrated development environment (IDE) focused on web application development. It supports popular web technologies such as JavaScript, TypeScript, React, Vue.js, and Node.js. CodeSandbox allows users to create, edit, and deploy web applications directly from the browser with zero setup. CodeSandbox is widely used for front-end development, rapid prototyping, sharing code snippets, and real-time collaborative coding. It provides GitHub integration, templates for common frameworks, and a cloud-based development container for full-stack projects. == Templates == == Limitations == Slower performance for larger tasks compared to native IDEs Some features require a paid subscription Performance and storage limits for free-tier users Limited offline capabilities
Pop music automation
Pop music automation is a field of study among musicians and computer scientists with a goal of producing successful pop music algorithmically. It is often based on the premise that pop music is especially formulaic, unchanging, and easy to compose. The idea of automating pop music composition is related to many ideas in algorithmic music, artificial intelligence (AI) and computational creativity. == History of automation in music == Algorithms (or, at the very least, formal sets of rules) have been used to compose music for centuries; the procedures used to plot voice-leading in counterpoint, for example, can often be reduced to algorithmic determinant. Now the term is usually reserved, however, for the use of formal procedures to make music without human intervention. Classical music automation software exists that generates music in the style of Mozart and Bach and jazz. Most notably, David Cope has written a software system called "Experiments in Musical Intelligence" (or "EMI") that is capable of analyzing and generalizing from existing music by a human composer to generate novel musical compositions in the same style. EMI's output is convincing enough to persuade human listeners that its music is human-generated to a high level of competence. Creativity research in jazz has focused on the process of improvisation and the cognitive demands that this places on a musical agent: reasoning about time, remembering and conceptualizing what has already been played, and planning ahead for what might be played next. Inevitably associated with pop music automation is pop music analysis. Projects in pop music automation may include, but are not limited to, ideas in melody creation and song development, vocal generation or improvement, automatic accompaniment and lyric composition. == Automatic accompaniment == Some systems exist that automatically choose chords to accompany a vocal melody in real-time. A user with no musical experience can create a song with instrumental accompaniment just by singing into a microphone. An example is a Microsoft Research project called Songsmith, which trains a Hidden Markov model using a music database and uses that model to select chords for new melodies. == Melody generation == Automatic melody generation is often done with a Markov chain, the states of the system become note or pitch values, and a probability vector for each note is constructed, completing a transition probability matrix (see below). An algorithm is constructed to produce an output note values based on the transition matrix weightings, which could be MIDI note values, frequency (Hz), or any other desirable metric. A second-order Markov chain can be introduced by considering the current state and also the previous state, as indicated in the second table. Higher, nth-order chains tend to "group" particular notes together, while 'breaking off' into other patterns and sequences occasionally. These higher-order chains tend to generate results with a sense of phrasal structure, rather than the 'aimless wandering' produced by a first-order system. == Lyric composition == Automated lyric creating software may take forms such as: Selecting words according to their rhythm The Tra-la-Lyrics system produces song lyrics, in Portuguese, for a given melody. This not only involves matching each word syllable with a note in the melody, but also matching the word's stress with the strong beats of the melody. Parsing existing pop music (e.g. for content or word choice) This involves natural language processing. Pablo Gervás has developed a noteworthy system called ASPERA that employs a case-based reasoning (CBR) approach to generating poetic formulations of a given input text via a composition of poetic fragments that are retrieved from a case-base of existing poems. Each poem fragment in the ASPERA case-base is annotated with a prose string that expresses the meaning of the fragment, and this prose string is used as the retrieval key for each fragment. Metrical rules are then used to combine these fragments into a well-formed poetic structure. Automatic analogy or story creation Programs like TALE-SPIN and The MINSTREL system represent a complex elaboration of this basis approach, distinguishing a range of character-level goals in the story from a range of author-level goals for the story. Systems like Bringsjord's BRUTUS can create stories with complex interpersonal themes like betrayal. On-line metaphor generation systems like 'Sardonicus' or 'Aristotle' can suggest lexical metaphors for a given descriptive goal (e.g., to describe a supermodel as skinny, the source terms “pencil”, “whip”, “whippet”, “rope”, “stick-insect” and “snake” are suggested). Free association of grouped words Using a language database (such as wordnet) one can create musings on a subject that may be weak grammatically but are still sensical. See such projects as the Flowerewolf automatic poetry generator or the Dada engine. == Software == === More or less free === BreathCube by xoxos. Simple lyrical vocal content is generated with simple music. CubeBreath by xoxos. Audio input is vocoded in tune with the music. Midi Internet Algorithmic Composition infno, infinite generator of electronic dance music and synth-pop. Algorithmic Trap, trap beat generator. === Commercial === Band in a box generates any element, potentially creates whole new songs from scratch. Musical Palette - Melody Composing Tool SongSmith: Automatic accompaniment for vocal melodies Ludwig 3.0 automatic accompaniment, writes arrangements for given instruments, plays its own songs for an infinitely long time. Automated Composing System creates music in many different styles