Grammar induction (or grammatical inference) is the process in machine learning of learning a formal grammar (usually as a collection of re-write rules or productions or alternatively as a finite-state machine or automaton of some kind) from a set of observations, thus constructing a model which accounts for the characteristics of the observed objects. More generally, grammatical inference is that branch of machine learning where the instance space consists of discrete combinatorial objects such as strings, trees and graphs. == Grammar classes == Grammatical inference has often been very focused on the problem of learning finite-state machines of various types (see the article Induction of regular languages for details on these approaches), since there have been efficient algorithms for this problem since the 1980s. Since the beginning of the century, these approaches have been extended to the problem of inference of context-free grammars and richer formalisms, such as multiple context-free grammars and parallel multiple context-free grammars. Other classes of grammars for which grammatical inference has been studied are combinatory categorial grammars, stochastic context-free grammars, contextual grammars and pattern languages. == Learning models == The simplest form of learning is where the learning algorithm merely receives a set of examples drawn from the language in question: the aim is to learn the language from examples of it (and, rarely, from counter-examples, that is, example that do not belong to the language). However, other learning models have been studied. One frequently studied alternative is the case where the learner can ask membership queries as in the exact query learning model or minimally adequate teacher model introduced by Angluin. == Methodologies == There is a wide variety of methods for grammatical inference. Two of the classic sources are Fu (1977) and Fu (1982). Duda, Hart & Stork (2001) also devote a brief section to the problem, and cite a number of references. The basic trial-and-error method they present is discussed below. For approaches to infer subclasses of regular languages in particular, see Induction of regular languages. A more recent textbook is de la Higuera (2010), which covers the theory of grammatical inference of regular languages and finite state automata. D'Ulizia, Ferri and Grifoni provide a survey that explores grammatical inference methods for natural languages. === Induction of probabilistic grammars === There are several methods for induction of probabilistic context-free grammars. === Grammatical inference by trial-and-error === The method proposed in Section 8.7 of Duda, Hart & Stork (2001) suggests successively guessing grammar rules (productions) and testing them against positive and negative observations. The rule set is expanded so as to be able to generate each positive example, but if a given rule set also generates a negative example, it must be discarded. This particular approach can be characterized as "hypothesis testing" and bears some similarity to Mitchel's version space algorithm. The Duda, Hart & Stork (2001) text provide a simple example which nicely illustrates the process, but the feasibility of such an unguided trial-and-error approach for more substantial problems is dubious. === Grammatical inference by genetic algorithms === Grammatical induction using evolutionary algorithms is the process of evolving a representation of the grammar of a target language through some evolutionary process. Formal grammars can easily be represented as tree structures of production rules that can be subjected to evolutionary operators. Algorithms of this sort stem from the genetic programming paradigm pioneered by John Koza. Other early work on simple formal languages used the binary string representation of genetic algorithms, but the inherently hierarchical structure of grammars couched in the EBNF language made trees a more flexible approach. Koza represented Lisp programs as trees. He was able to find analogues to the genetic operators within the standard set of tree operators. For example, swapping sub-trees is equivalent to the corresponding process of genetic crossover, where sub-strings of a genetic code are transplanted into an individual of the next generation. Fitness is measured by scoring the output from the functions of the Lisp code. Similar analogues between the tree structured lisp representation and the representation of grammars as trees, made the application of genetic programming techniques possible for grammar induction. In the case of grammar induction, the transplantation of sub-trees corresponds to the swapping of production rules that enable the parsing of phrases from some language. The fitness operator for the grammar is based upon some measure of how well it performed in parsing some group of sentences from the target language. In a tree representation of a grammar, a terminal symbol of a production rule corresponds to a leaf node of the tree. Its parent nodes corresponds to a non-terminal symbol (e.g. a noun phrase or a verb phrase) in the rule set. Ultimately, the root node might correspond to a sentence non-terminal. === Grammatical inference by greedy algorithms === Like all greedy algorithms, greedy grammar inference algorithms make, in iterative manner, decisions that seem to be the best at that stage. The decisions made usually deal with things like the creation of new rules, the removal of existing rules, the choice of a rule to be applied or the merging of some existing rules. Because there are several ways to define 'the stage' and 'the best', there are also several greedy grammar inference algorithms. These context-free grammar generating algorithms make the decision after every read symbol: Lempel-Ziv-Welch algorithm creates a context-free grammar in a deterministic way such that it is necessary to store only the start rule of the generated grammar. Sequitur and its modifications. These context-free grammar generating algorithms first read the whole given symbol-sequence and then start to make decisions: Byte pair encoding and its optimizations. === Distributional learning === A more recent approach is based on distributional learning. Algorithms using these approaches have been applied to learning context-free grammars and mildly context-sensitive languages and have been proven to be correct and efficient for large subclasses of these grammars. === Learning of pattern languages === Angluin defines a pattern to be "a string of constant symbols from Σ and variable symbols from a disjoint set". The language of such a pattern is the set of all its nonempty ground instances i.e. all strings resulting from consistent replacement of its variable symbols by nonempty strings of constant symbols. A pattern is called descriptive for a finite input set of strings if its language is minimal (with respect to set inclusion) among all pattern languages subsuming the input set. Angluin gives a polynomial algorithm to compute, for a given input string set, all descriptive patterns in one variable x. To this end, she builds an automaton representing all possibly relevant patterns; using sophisticated arguments about word lengths, which rely on x being the only variable, the state count can be drastically reduced. Erlebach et al. give a more efficient version of Angluin's pattern learning algorithm, as well as a parallelized version. Arimura et al. show that a language class obtained from limited unions of patterns can be learned in polynomial time. === Pattern theory === Pattern theory, formulated by Ulf Grenander, is a mathematical formalism to describe knowledge of the world as patterns. It differs from other approaches to artificial intelligence in that it does not begin by prescribing algorithms and machinery to recognize and classify patterns; rather, it prescribes a vocabulary to articulate and recast the pattern concepts in precise language. In addition to the new algebraic vocabulary, its statistical approach was novel in its aim to: Identify the hidden variables of a data set using real world data rather than artificial stimuli, which was commonplace at the time. Formulate prior distributions for hidden variables and models for the observed variables that form the vertices of a Gibbs-like graph. Study the randomness and variability of these graphs. Create the basic classes of stochastic models applied by listing the deformations of the patterns. Synthesize (sample) from the models, not just analyze signals with it. Broad in its mathematical coverage, pattern theory spans algebra and statistics, as well as local topological and global entropic properties. == Applications == The principle of grammar induction has been applied to other aspects of natural language processing, and has been applied (among many other problems) to semantic parsing, natural language understanding, example-based translation, language acquisition, grammar-based compre
Are You Dead?
Are You Dead? (Chinese: 死了么; pinyin: Sǐleme), also known by its English name Demumu, is a Chinese application designed for young people living alone. It requires setting up one emergency contact and sends automatic notifications if the user has not checked in via the app for consecutive days. The app was released on the App Store on 10 June 2025. In early January 2026, the application gained popularity due to its name and the issue of safety for people living alone, and ranked high on the list of paid applications in the Chinese region of the Apple App Store before being removed. The app's rise in popularity sparked discussions about taboos about death in China. == History == Are You Dead? was founded and operated independently by three people born in the 1990s, and developed in a way that involved remote collaboration in their spare time. According to the New Yellow River report, Guo, the product manager, said that the application was designed for young people and that the inspiration came from the discussion of netizens on social platforms about "an app that everyone must have and will definitely download" that he observed two or three years ago. The name was also "not their original creation". After realizing its potential demand and social significance, the team successfully registered the name and completed the product development in about a month. Regarding the development entity, the New Yellow River cited information from the Apple App Store that the application was developed by Yuejing (Zhengzhou) Technology Service Co., Ltd. According to Tianyancha information, the company was established in March 2025 with a registered capital of 100,000 yuan. === Rise in popularity === The app has been generating buzz on social media since 9 January 2026, due to its name and the topic of safety for people living alone. Around 10 January, it topped the Apple paid app chart. As of 10:00 a.m. on January 11, it ranked first in the App Store paid app chart. It also ranked highly in the utility app chart; it ranked first or second in the paid utility app charts in the United States, Singapore and Hong Kong, and first or fourth in Australia and Spain. The app was subsequently removed from the Apple App Store in China. In terms of functionality and usage, First Financial praised the product for its "simple interface and single function," but pointed out that the interface lacks a display of consecutive check-in days, and there is also the possibility that users may forget to check in, leading to the mistaken issuance of reminders. In addition, since the application mainly relies on email reminders and lacks SMS or telephone notifications, it does not conform to Chinese social habits; the untimely notifications also make the application more like a "death notification" tool, losing its early warning significance for emergency rescue. Hu Xijin, former editor-in-chief of the Global Times, commented on the application on Weibo that it is "really good and can help many lonely elderly people." The Beijing News Quick Review pointed out that the role of technical tools is limited and needs to be connected with real support such as community patrols and liaison mechanisms. Due to the price increase, there have also been questions about the motivation for the price increase. The app's rise in popularity sparked discussions about taboos about death in China. Regarding the popularity of the application, both Southern Metropolis Daily and The Beijing News commented that it reflects the public issue of the risks of living alone and reflects the general anxiety of the living alone group about dying alone. Shangguan News further pointed out that although such technology products provide a certain "low-cost sense of security", their "cold notifications" may not only cause false alarms, but also highlight the embarrassing reality that "there is no one to fill in the emergency contact". It also emphasized that algorithms or applications cannot bring true happiness and called on society to reconstruct a support network full of humanistic care while relying on technology. The name of the application has also sparked controversy. Most netizens believe that the name "Are You Dead?" is unlucky and makes it awkward to share the application. They suggest changing it to a milder name such as "Are You Alive?". Hu Xijin also said that the name change could "give the elderly who use it more psychological comfort" and "believe that the application will become more popular after the name change". Some people also believe that this straightforward name just points out the real dilemma faced by people living alone and has a special meaning. BBC News commented that the name "Are You Dead" is playing a word game with Ele.me (Chinese: 饿了么; pinyin: Èleme) and the pronunciation is also similar. Legal professionals believe that its name is highly similar to Ele.me and may cause confusion. They also raised the possibility of trademark infringement and unfair competition. However, the developers said that the application is developed for young people and death is not a sensitive topic. They will "consider launching a new application that is more suitable for middle-aged and elderly people". They have not yet received any name change requests from relevant departments. On the evening of 13 January 2026, the Are You Dead? team announced that it would change its name to the English brand name Demumu in the upcoming new version. On 11 January, the development team also issued a statement through its official Weibo account, stating that it would study the renaming suggestion and plan to enrich the SMS reminder function, consider adding the message function and explore the direction of age-friendly products; it also stated that it would launch an 8 yuan paid plan to cover the costs of SMS, servers, etc., and welcomed investors to discuss cooperation. In terms of financing and valuation, it plans to sell 10% of the company's shares for 1 million yuan and proposed a valuation of 10 million yuan. On the evening of January 15, the application was removed from the app store in mainland China. == Functions == The application does not require users to enter phone numbers or other information to register. After filling in their name and setting an emergency contact, users can click the sign-in button every day. If they fail to sign in for two consecutive days, the system will send an email reminder to the emergency contact the next day. In addition, users can also bind a smart bracelet to monitor physiological signs, pre-designate a hearse driver and funeral music, and trigger the "one-click body collection" function when no pulse is detected. The application was initially available for free download, but a one yuan paid download option was introduced at the end of 2025. In January 2026, the application team issued a statement saying that an 8 yuan paid option would be launched based on the costs of SMS, servers, etc.
Emotion recognition
Emotion recognition is the process of identifying human emotion. People vary widely in their accuracy at recognizing the emotions of others. Use of technology to help people with emotion recognition is a relatively nascent research area. Generally, the technology works best if it uses multiple modalities in context. To date, the most work has been conducted on automating the recognition of facial expressions from video, spoken expressions from audio, written expressions from text, and physiology as measured by wearables. == Human == Humans show a great deal of variability in their abilities to recognize emotion. A key point to keep in mind when learning about automated emotion recognition is that there are several sources of "ground truth", or truth about what the real emotion is. Suppose we are trying to recognize the emotions of Alex. One source is "what would most people say that Alex is feeling?" In this case, the 'truth' may not correspond to what Alex feels, but may correspond to what most people would say it looks like Alex feels. For example, Alex may actually feel sad, but he puts on a big smile and then most people say he looks happy. If an automated method achieves the same results as a group of observers it may be considered accurate, even if it does not actually measure what Alex truly feels. Another source of 'truth' is to ask Alex what he truly feels. This works if Alex has a good sense of his internal state, and wants to tell you what it is, and is capable of putting it accurately into words or a number. However, some people are alexithymic and do not have a good sense of their internal feelings, or they are not able to communicate them accurately with words and numbers. In general, getting to the truth of what emotion is actually present can take some work, can vary depending on the criteria that are selected, and will usually involve maintaining some level of uncertainty. == Automatic == Decades of scientific research have been conducted developing and evaluating methods for automated emotion recognition. There is now an extensive literature proposing and evaluating hundreds of different kinds of methods, leveraging techniques from multiple areas, such as signal processing, machine learning, computer vision, and speech processing. Different methodologies and techniques may be employed to interpret emotion such as Bayesian networks. , Gaussian Mixture models and Hidden Markov Models and deep neural networks. === Approaches === The accuracy of emotion recognition is usually improved when it combines the analysis of human expressions from multimodal forms such as texts, physiology, audio, or video. Different emotion types are detected through the integration of information from facial expressions, body movement and gestures, and speech. The technology is said to contribute in the emergence of the so-called emotional or emotive Internet. The existing approaches in emotion recognition to classify certain emotion types can be generally classified into three main categories: knowledge-based techniques, statistical methods, and hybrid approaches. ==== Knowledge-based techniques ==== Knowledge-based techniques (sometimes referred to as lexicon-based techniques), utilize domain knowledge and the semantic and syntactic characteristics of text and potentially spoken language in order to detect certain emotion types. In this approach, it is common to use knowledge-based resources during the emotion classification process such as WordNet, SenticNet, ConceptNet, and EmotiNet, to name a few. One of the advantages of this approach is the accessibility and economy brought about by the large availability of such knowledge-based resources. A limitation of this technique on the other hand, is its inability to handle concept nuances and complex linguistic rules. Knowledge-based techniques can be mainly classified into two categories: dictionary-based and corpus-based approaches. Dictionary-based approaches find opinion or emotion seed words in a dictionary and search for their synonyms and antonyms to expand the initial list of opinions or emotions. Corpus-based approaches on the other hand, start with a seed list of opinion or emotion words, and expand the database by finding other words with context-specific characteristics in a large corpus. While corpus-based approaches take into account context, their performance still vary in different domains since a word in one domain can have a different orientation in another domain. ==== Statistical methods ==== Statistical methods commonly involve the use of different supervised machine learning algorithms in which a large set of annotated data is fed into the algorithms for the system to learn and predict the appropriate emotion types. Machine learning algorithms generally provide more reasonable classification accuracy compared to other approaches, but one of the challenges in achieving good results in the classification process, is the need to have a sufficiently large training set. Some of the most commonly used machine learning algorithms include Support Vector Machines (SVM), Naive Bayes, and Maximum Entropy. Deep learning, which is under the unsupervised family of machine learning, is also widely employed in emotion recognition. Well-known deep learning algorithms include different architectures of Artificial Neural Network (ANN) such as Convolutional Neural Network (CNN), Long Short-term Memory (LSTM), and Extreme Learning Machine (ELM). The popularity of deep learning approaches in the domain of emotion recognition may be mainly attributed to its success in related applications such as in computer vision, speech recognition, and Natural Language Processing (NLP). ==== Hybrid approaches ==== Hybrid approaches in emotion recognition are essentially a combination of knowledge-based techniques and statistical methods, which exploit complementary characteristics from both techniques. Some of the works that have applied an ensemble of knowledge-driven linguistic elements and statistical methods include sentic computing and iFeel, both of which have adopted the concept-level knowledge-based resource SenticNet. The role of such knowledge-based resources in the implementation of hybrid approaches is highly important in the emotion classification process. Since hybrid techniques gain from the benefits offered by both knowledge-based and statistical approaches, they tend to have better classification performance as opposed to employing knowledge-based or statistical methods independently. A downside of using hybrid techniques however, is the computational complexity during the classification process. === Datasets === Data is an integral part of the existing approaches in emotion recognition and in most cases it is a challenge to obtain annotated data that is necessary to train machine learning algorithms. For the task of classifying different emotion types from multimodal sources in the form of texts, audio, videos or physiological signals, the following datasets are available: HUMAINE: provides natural clips with emotion words and context labels in multiple modalities Belfast database: provides clips with a wide range of emotions from TV programs and interview recordings SEMAINE: provides audiovisual recordings between a person and a virtual agent and contains emotion annotations such as angry, happy, fear, disgust, sadness, contempt, and amusement IEMOCAP: provides recordings of dyadic sessions between actors and contains emotion annotations such as happiness, anger, sadness, frustration, and neutral state eNTERFACE: provides audiovisual recordings of subjects from seven nationalities and contains emotion annotations such as happiness, anger, sadness, surprise, disgust, and fear DEAP: provides electroencephalography (EEG), electrocardiography (ECG), and face video recordings, as well as emotion annotations in terms of valence, arousal, and dominance of people watching film clips DREAMER: provides electroencephalography (EEG) and electrocardiography (ECG) recordings, as well as emotion annotations in terms of valence, dominance of people watching film clips MELD: is a multiparty conversational dataset where each utterance is labeled with emotion and sentiment. MELD provides conversations in video format and hence suitable for multimodal emotion recognition and sentiment analysis. MELD is useful for multimodal sentiment analysis and emotion recognition, dialogue systems and emotion recognition in conversations. MuSe: provides audiovisual recordings of natural interactions between a person and an object. It has discrete and continuous emotion annotations in terms of valence, arousal and trustworthiness as well as speech topics useful for multimodal sentiment analysis and emotion recognition. UIT-VSMEC: is a standard Vietnamese Social Media Emotion Corpus (UIT-VSMEC) with about 6,927 human-annotated sentences with six emotion labels, contributing to emotion recognition research in Vietnamese
Subject indexing
Subject indexing is the act of describing or classifying a document by index terms, keywords, or other symbols in order to indicate what different documents are about, to summarize their contents or to increase findability. In other words, the objective is to identify and describe the subject of documents. Indexes are constructed, separately, on three distinct levels: terms in a document, such as a book; objects in a collection, such as a library; and documents (such as books and articles) within a field of knowledge. Subject indexing is used in information retrieval especially to create bibliographic indexes to retrieve documents on a particular subject. Examples of academic indexing services are Zentralblatt MATH, Chemical Abstracts, and PubMed. The index terms were mostly assigned by experts but author keywords are also common. The process of indexing begins with any analysis of the subject of the document. The indexer must then identify terms that appropriately identify the subject, either by extracting words directly from the document or assigning words from a controlled vocabulary. The terms in the index are then presented in a systematic order. Indexers must decide how many terms to include and how specific the terms should be. Together this gives a depth of indexing. == Subject analysis == The first step in indexing is to decide on the subject matter of the document. In manual indexing, the indexer would consider the subject matter in terms of answer to a set of questions such as "Does the document deal with a specific product, condition or phenomenon?". As the analysis is influenced by the knowledge and experience of the indexer, it follows that two indexers may analyze the content differently and so come up with different index terms. This will impact on the success of retrieval. === Automatic vs. manual subject analysis === Automatic indexing follows set processes of analyzing frequencies of word patterns and comparing results to other documents in order to assign to subject categories. This requires no understanding of the material being indexed. This leads to more uniform indexing but at the expense of the true meaning being interpreted. A computer program will not understand the meaning of statements and may therefore fail to assign some relevant terms or assign incorrectly. Human indexers focus their attention on certain parts of the document such as the title, abstract, summary and conclusions, as analyzing the full text in depth is costly and time-consuming. An automated system takes away the time limit and allows the entire document to be analyzed, but also has the option to be directed to particular parts of the document. == Term selection == The second stage of indexing involves the translation of the subject analysis into a set of index terms. This can involve extracting from the document or assigning from a controlled vocabulary. With the ability to conduct a full text search widely available, many people have come to rely on their own expertise in conducting information searches and full text search has become very popular. Subject indexing and its experts, professional indexers, catalogers, and librarians, remains crucial to information organization and retrieval. These experts understand controlled vocabularies and are able to find information that cannot be located by full text search. The cost of expert analysis to create subject indexing is not easily compared to the cost of hardware, software and labor to manufacture a comparable set of full-text, fully searchable materials. With new web applications that allow every user to annotate documents, social tagging has gained popularity especially in the Web. One application of indexing, the book index, remains relatively unchanged despite the information revolution. === Extraction/Derived indexing === Extraction indexing involves taking words directly from the document. It uses natural language and lends itself well to automated techniques where word frequencies are calculated and those with a frequency over a pre-determined threshold are used as index terms. A stop-list containing common words (such as "the", "and") would be referred to and such stop words would be excluded as index terms. Automated extraction indexing may lead to loss of meaning of terms by indexing single words as opposed to phrases. Although it is possible to extract commonly occurring phrases, it becomes more difficult if key concepts are inconsistently worded in phrases. Automated extraction indexing also has the problem that, even with use of a stop-list to remove common words, some frequent words may not be useful for allowing discrimination between documents. For example, the term glucose is likely to occur frequently in any document related to diabetes. Therefore, use of this term would likely return most or all the documents in the database. Post-coordinated indexing where terms are combined at the time of searching would reduce this effect but the onus would be on the searcher to link appropriate terms as opposed to the information professional. In addition terms that occur infrequently may be highly significant for example a new drug may be mentioned infrequently but the novelty of the subject makes any reference significant. One method for allowing rarer terms to be included and common words to be excluded by automated techniques would be a relative frequency approach where frequency of a word in a document is compared to frequency in the database as a whole. Therefore, a term that occurs more often in a document than might be expected based on the rest of the database could then be used as an index term, and terms that occur equally frequently throughout will be excluded. Another problem with automated extraction is that it does not recognize when a concept is discussed but is not identified in the text by an indexable keyword. Since this process is based on simple string matching and involves no intellectual analysis, the resulting product is more appropriately known as a concordance than an index. === Assignment indexing === An alternative is assignment indexing where index terms are taken from a controlled vocabulary. This has the advantage of controlling for synonyms as the preferred term is indexed and synonyms or related terms direct the user to the preferred term. This means the user can find articles regardless of the specific term used by the author and saves the user from having to know and check all possible synonyms. It also removes any confusion caused by homographs by inclusion of a qualifying term. A third advantage is that it allows the linking of related terms whether they are linked by hierarchy or association, e.g. an index entry for an oral medication may list other oral medications as related terms on the same level of the hierarchy but would also link to broader terms such as treatment. Assignment indexing is used in manual indexing to improve inter-indexer consistency as different indexers will have a controlled set of terms to choose from. Controlled vocabularies do not completely remove inconsistencies as two indexers may still interpret the subject differently. == Index presentation == The final phase of indexing is to present the entries in a systematic order. This may involve linking entries. In a pre-coordinated index the indexer determines the order in which terms are linked in an entry by considering how a user may formulate their search. In a post-coordinated index, the entries are presented singly and the user can link the entries through searches, most commonly carried out by computer software. Post-coordination results in a loss of precision in comparison to pre-coordination. == Depth of indexing == Indexers must make decisions about what entries should be included and how many entries an index should incorporate. The depth of indexing describes the thoroughness of the indexing process with reference to exhaustivity and specificity. === Exhaustivity === An exhaustive index is one which lists all possible index terms. Greater exhaustivity gives a higher recall, or more likelihood of all the relevant articles being retrieved, however, this occurs at the expense of precision. This means that the user may retrieve a larger number of irrelevant documents or documents which only deal with the subject in little depth. In a manual system a greater level of exhaustivity brings with it a greater cost as more man-hours are required. The additional time taken in an automated system would be much less significant. At the other end of the scale, in a selective index only the most important aspects are covered. Recall is reduced in a selective index as if an indexer does not include enough terms, a highly relevant article may be overlooked. Therefore, indexers should strive for a balance and consider what the document may be used. They may also have to consider the implications of time and expense. === Specificity === The specificity describes how closel
Knowledge spillover
Knowledge spillover is an exchange of ideas among individuals. Knowledge spillover is usually replaced by terminations of technology spillover, R&D spillover and/or spillover (economics) when the concept is specific to technology management and innovation economics. In knowledge management economics, knowledge spillovers are non-rival knowledge market costs incurred by a party not agreeing to assume the costs that has a spillover effect of stimulating technological improvements in a neighbor through one's own innovation. Such innovations often come from specialization within an industry. There are two kinds of knowledge spillovers: internal and external. Internal knowledge spillover occurs if there is a positive impact of knowledge between individuals within an organization that produces goods and/or services. An external knowledge spillover occurs when the positive impact of knowledge is between individuals outside of a production organization. Marshall–Arrow–Romer (MAR) spillovers, Porter spillovers and Jacobs spillovers are three types of spillovers. == Conceptualizations == === Marshall–Arrow–Romer === Marshall–Arrow–Romer (MAR) spillover has its origins in 1890, where the English economist Alfred Marshall developed a theory of knowledge spillovers. Knowledge spillovers later were extended by economists Kenneth Arrow (1962) and Paul Romer (1986). In 1992, Edward Glaeser, Hedi Kallal, José Scheinkman, and Andrei Shleifer pulled together the Marshall–Arrow–Romer views on knowledge spillovers and accordingly named the view MAR spillover in 1992. Under the Marshall–Arrow–Romer (MAR) spillover view, the proximity of firms within a common industry often affects how well knowledge travels among firms to facilitate innovation and growth. The closer the firms are to one another, the greater the MAR spillover. The exchange of ideas is largely from employee to employee, in that employees from different firms in an industry exchange ideas about new products and new ways to produce goods. The opportunity to exchange ideas that lead to innovations key to new products and improved production methods. Research on the Cambridge IT Cluster (UK) suggests that technological knowledge spillovers might only happen rarely and are less important than other cluster benefits such as labour market pooling. === Porter === Porter (1990), like MAR, argues that knowledge spillovers in specialized, geographically concentrated industries stimulate growth. He insists, however, that local competition, as opposed to local monopoly, fosters the pursuit and rapid adoption of innovation. He gives examples of Italian ceramics and gold jewellery industries, in which hundreds of firms are located together and fiercely compete to innovate since the alternative to innovation is demise. Porter's externalities are maximized in cities with geographically specialized, competitive industries. === Jacobs === Under the Jacobs spillover view, the proximity of firms from different industries affect how well knowledge travels among firms to facilitate innovation and growth. This is in contrast to MAR spillovers, which focus on firms in a common industry. The diverse proximity of a Jacobs spillover brings together ideas among individuals with different perspectives to encourage an exchange of ideas and foster innovation in an industrially diverse environment. Developed in 1969 by urbanist Jane Jacobs and John Jackson the concept that Detroit’s shipbuilding industry from the 1830s was the critical antecedent leading to the 1890s development of the auto industry in Detroit since the gasoline engine firms easily transitioned from building gasoline engines for ships to building them for automobiles. == Incoming and outgoing spillovers == Knowledge spillover has asymmetric directions. The focal entity and receives or outflows know-how to others, creating incoming and outgoing spillovers. Cassiman and Veugelers (2002) use survey data and estimate incoming and outgoing spillover and study the economic impacts. Incoming spillover increases growth opportunity and productivity improvements of receivers, while outgoing spillover leads to free rider problem in the technology competition. Chen et al. (2013) use econometric method to gauge incoming spillover, a way that applies for all companies without survey. They find that incoming spillover explains R&D profits of industrial firms. == Policy implications == As information is largely non-rival in nature, certain measures must be taken to ensure that, for the originator, the information remains a private asset. As the market cannot do this efficiently, public regulations have been implemented to facilitate a more appropriate equilibrium. As a result, the concept of intellectual property rights have developed and ensure the ability of entrepreneurs to temporarily hold on to the profitability of their ideas through patents, copyrights, trade secrets, and other governmental safeguards. Conversely, such barriers to entry prevent the exploitation of informational developments by rival firms within an industry. For example, Wang (2023) indicates that technology spillovers are reduced by 27% to 51% when trade secrets laws are implemented by the Uniform Trade Secrets Act in the US. On the other hand, when the research and development of a private firm results in a social benefit, unaccounted for within the market price, often greater than the private return of the firm's research, then a subsidy to offset the underproduction of that benefit might be offered to the firm in return for its continued output of that benefit. Government subsidies are often controversial, and while they might often result in a more appropriate social equilibrium, they could also lead to undesirable political repercussions as such a subsidy must come from taxpayers, some of whom may not directly benefit from the researching firm's subsidized knowledge spillover. The concept of knowledge spillover is also used to justify subsidies to foreign direct investment, as foreign investors help diffuse technology among local firms. == Examples == Business parks are a good specific example of concentrated businesses that may benefit from MAR spillover. Many semiconductor firms intentionally located their research and development facilities in Silicon Valley to take advantage of MAR spillover. In addition, the film industry in Los Angeles, California, and elsewhere relies on a geographic concentration of specialists (directors, producers, scriptwriters, and set designers) to bring together narrow aspects of movie-making into a final product. A general example of a knowledge spillover could be the collective growth associated with the research and development of online social networking tools like Facebook, YouTube, and Twitter. Such tools have not only created a positive feedback loop, and a host of originally unintended benefits for their users, but have also created an explosion of new software, programming platforms, and conceptual breakthroughs that have perpetuated the development of the industry as a whole. The advent of online marketplaces, the utilization of user profiles, the widespread democratization of information, and the interconnectivity between tools within the industry have all been products of each tool's individual developments. These developments have since spread outside the industry into the mainstream media as news and entertainment firms have developed their own market feedback applications within the tools themselves, and their own versions of online networking tools (e.g. CNN’s iReport).
Automated parking system
An automated (car) parking system (APS) is a mechanical system designed to minimize the area and/or volume required for parking cars. Like a multi-story parking garage, an APS provides parking for cars on multiple levels stacked vertically to maximize the number of parking spaces while minimizing land usage. The APS, however, utilizes a mechanical system to transport cars to and from parking spaces (rather than the driver) in order to eliminate much of the space wasted in a multi-story parking garage. While a multi-story parking garage is similar to multiple parking lots stacked vertically, an APS is more similar to an automated storage and retrieval system for cars. Parking systems are generally powered by electric motors or hydraulic pumps that move vehicles into a storage position.The paternoster (shown animated at the right) is an example of one of the earliest and most common types of APS. APS are also generically known by a variety of other names, including:automated parking facility (APF), automated vehicle storage and retrieval system (AVSRS), car parking system, mechanical parking, and robotic parking garage. == History == The concept for the automated parking system was and is driven by two factors: a need for parking spaces and a scarcity of available land. The earliest use of an APS was in Paris, France in 1905 at the Garage Rue de Ponthieu. The APS consisted of a groundbreaking multi-story concrete structure with an internal car elevator to transport cars to upper levels where attendants parked the cars. In the 1920s, a Ferris wheel-like APS (for cars rather than people) called a paternoster system became popular as it could park eight cars in the ground space normally used for parking two cars. Mechanically simple with a small footprint, the paternoster was easy to use in many places, including inside buildings. At the same time, Kent Automatic Garages was installing APS with capacities exceeding 1,000 cars. The “ferris-wheel,” or paternoster system — was created by the Westinghouse Corporation in 1923 and subsequently built in 1932 on Chicago's Monroe Street. The Nash Motor Company created the first glass-enclosed version of this system for the Chicago Century of Progress Exhibition in 1933 The first driverless parking garage opened in 1951 in Washington, D.C., but was replaced with office space due to increasing land values. APS saw a spurt of interest in the U.S. in the late 1940s and 1950s with the Bowser, Pigeon Hole and Roto Park systems. In 1957, 74 Bowser, Pigeon Hole systems were installed, and some of these systems remain in operation. However, interest in APS in the U.S. waned due to frequent mechanical problems and long waiting times for patrons to retrieve their cars. In the United Kingdom, the Auto Stacker opened in 1961 in Woolwich, south east London, but proved equally difficult to operate. Interest in APS in the U.S. was renewed in the 1990s, and there were 25 major current and planned APS projects (representing nearly 6,000 parking spaces) in 2012. The first American robotic parking garage opened in 2002 in Hoboken, New Jersey. While interest in the APS in the U.S. languished until the 1990s, Europe, Asia and Central America had been installing more technically advanced APS since the 1970s. In the early 1990s, nearly 40,000 parking spaces were being built annually using the paternoster APS in Japan. In 2012, there are an estimated 1.6 million APS parking spaces in Japan. The ever-increasing scarcity of available urban land (urbanization) and increase of the number of cars in use (motorization) have combined with sustainability and other quality-of-life issues to renew interest in APS as alternatives to multi-storey car parks, on-street parking, and parking lots. == Largest systems == The largest Automated Parking Facility in the world is in Al Jahra, Kuwait, and provides 2,314 parking spaces. The world's fastest Automated Parking System is in Wolfsburg, Germany, with a retrieval time of 1 minute and 44 seconds. The largest APS in Europe is at Dokk1 in Aarhus, Denmark, and provides 1,000 parking spaces via 20 car lifts. == Space saving == All APS take advantage of a common concept to decrease the area of parking spaces - removing the driver and passengers from the car before it is parked. With either fully automated or semi-automated APS, the car is driven up to an entry point to the APS and the driver and passengers exit the car. The car is then moved automatically or semi-automatically (with some attendant action required) to its parking space. The space-saving provided by the APS, compared to the multi-story parking garage, is derived primarily from a significant reduction in space not directly related to the parking of the car: Parking space width and depth (and distances between parking spaces) are dramatically reduced since no allowance need be made for driving the car into the parking space or for the opening of car doors (for drivers and passengers) No driving lanes or ramps are needed to drive the car to/from the entrance/exit to a parking space Ceiling height is minimized since there is no pedestrian traffic (drivers and passengers) in the parking area, and No walkways, stairways or elevators are needed to accommodate pedestrians in the parking area. With the elimination of ramps, driving lanes, pedestrians and the reduction in ceiling heights, the APS requires substantially less structural material than the multi-story parking garage. Many APS utilize a steel framework (some use thin concrete slabs) rather than the monolithic concrete design of the multi-story parking garage. These factors contribute to an overall volume reduction and further space savings for the APS. == Other considerations == In addition to the space saving, many APS designs provide a number of secondary benefits: The parked cars and their contents are more secure since there is no public access to parked cars Minor parking lot damage such as scrapes and dents are eliminated Drivers and passengers are safer not having to walk through parking lots or garages Driving around in search of a parking space is eliminated, thereby reducing engine emissions and wasted time Only minimal ventilation and lighting systems are needed Handicap access is improved The volume and visual impact of the parking structure is minimized Shorter construction time === Problems === There have been a number of problems with robotic parking systems, particularly in the United States. The systems work well in balanced throughput situations like shopping malls and train stations, but they are unsuited to high peak volume applications like rush hour usage or stadiums and they suffer from technical problems. Further, parkers not familiar with the system may cause problems, for example by failing to push the button to alert a fully automated system to the presence of a car to be parked. In London around 40 vehicles were trapped for two years in CBRE's system. == Fully automated vs semi-automated == Fully automated parking systems operate much like robotic valet parking. The driver drives the car into an APS entry (transfer) area. The driver and all passengers exit the car. The driver uses an automated terminal nearby for payment and receipt of a ticket. When driver and passengers have left the entry area, the mechanical system lifts the car and transports it to a pre-determined parking space in the system. More sophisticated fully automated APS will obtain the dimensions of cars on entry in order to place them in the smallest available parking space. The driver retrieves a car by inserting a ticket or code into an automated terminal. The APS lifts the car from its parking space and delivers it to an exit area. Most often, the retrieved car has been oriented to eliminate the need for the driver to back out. Fully automated APS theoretically eliminate the need for parking attendants. Semi-automated APS also use a mechanical system of some type to move a car to its parking space, however putting the car into and/or the operation of the system requires some action by an attendant or the driver. The choice between fully and semi-automated APS is often a matter of space and cost, however large capacity (> 100 cars) tend to be fully automated. == Applications == By virtue of their relatively smaller volume and mechanized parking systems, APS are often used in locations where a multi-story parking garage would be too large, too costly or impractical. Examples of such applications include, under or inside existing or new structures, between existing structures and in irregularly shaped areas. APS can also be applied in situations similar to multi-storey parking garages such as freestanding above ground, under buildings above grade and under buildings below grade. == Costs == The direct comparison of costs between an APS and a multi-story parking garage can be complicated by many variables such as capacity, land costs, area shape, number and location of entranc
Hindley–Milner type system
A Hindley–Milner (HM) type system is a classical type system for the lambda calculus with parametric polymorphism. It is also known as Damas–Milner or Damas–Hindley–Milner. It was first described by J. Roger Hindley and later rediscovered by Robin Milner. Luis Damas contributed a close formal analysis and proof of the method in his PhD thesis. Among HM's more notable properties are its completeness and its ability to infer the most general type of a given program without programmer-supplied type annotations or other hints. Algorithm W is an efficient type inference method in practice and has been successfully applied on large code bases, although it has a high theoretical complexity. HM is preferably used for functional programming languages. It was first implemented as part of the type system of the programming language ML. Since then, HM has been extended in various ways, most notably with type class constraints like those in Haskell. == Introduction == As a type inference method, Hindley–Milner is able to deduce the types of variables, expressions and functions from programs written in an entirely untyped style. Being scope sensitive, it is not limited to deriving the types only from a small portion of source code, but rather from complete programs or modules. Being able to cope with parametric types, too, it is core to the type systems of many functional programming languages. It was first applied in this manner in the ML programming language. The origin is the type inference algorithm for the simply typed lambda calculus that was devised by Haskell Curry and Robert Feys in 1958. In 1969, J. Roger Hindley extended this work and proved that their algorithm always inferred the most general type. In 1978, Robin Milner, independently of Hindley's work, provided an equivalent algorithm, Algorithm W. In 1982, Luis Damas finally proved that Milner's algorithm is complete and extended it to support systems with polymorphic references. === Monomorphism vs. polymorphism === In the simply typed lambda calculus, types T are either atomic type constants or function types of form T → T {\displaystyle T\rightarrow T} . Such types are monomorphic. Typical examples are the types used in arithmetic values: 3 : N u m b e r a d d 3 4 : N u m b e r a d d : N u m b e r → N u m b e r → N u m b e r {\displaystyle {\begin{array}{ll}3&:{\mathtt {Number}}\\{\mathtt {add}}\ 3\ 4&:{\mathtt {Number}}\\{\mathtt {add}}&:{\mathtt {Number}}\rightarrow {\mathtt {Number}}\rightarrow {\mathtt {Number}}\end{array}}} Contrary to this, the untyped lambda calculus is neutral to typing at all, and many of its functions can be meaningfully applied to all type of arguments. The trivial example is the identity function i d ≡ λ x . x {\displaystyle {\mathtt {id}}\equiv \lambda x.x} which simply returns whatever value it is applied to. Less trivial examples include parametric types like lists. While polymorphism in general means that operations accept values of more than one type, the polymorphism used here is parametric. One finds the notation of type schemes in the literature, too, emphasizing the parametric nature of the polymorphism. Additionally, constants may be typed with (quantified) type variables. For example, the following type schemes quantify universally over α {\displaystyle \alpha } , meaning that they are true for all possible α {\displaystyle \alpha } : c o n s : ∀ α . α → L i s t α → L i s t α n i l : ∀ α . L i s t α i d : ∀ α . α → α {\displaystyle {\begin{array}{ll}{\mathtt {cons}}&:\forall \alpha .\alpha \rightarrow {\mathtt {List}}\ \alpha \rightarrow {\mathtt {List}}\ \alpha \\{\mathtt {nil}}&:\forall \alpha .{\mathtt {List}}\ \alpha \\{\mathtt {id}}&:\forall \alpha .\alpha \rightarrow \alpha \end{array}}} Polymorphic types can become monomorphic by consistent substitution of their variables. Examples of monomorphic instances are: i d ′ : S t r i n g → S t r i n g n i l ′ : L i s t N u m b e r {\displaystyle {\begin{array}{ll}{\mathtt {id}}'&:{\mathtt {String}}\rightarrow {\mathtt {String}}\\{\mathtt {nil}}'&:{\mathtt {List}}\ {\mathtt {Number}}\end{array}}} More generally, types are polymorphic when they contain type variables, while types without them are monomorphic. Contrary to the type systems used for example in Pascal (1970) or C (1972), which only support monomorphic types, HM is designed with emphasis on parametric polymorphism. The successors of the languages mentioned, like C++ (1985), focused on different types of polymorphism, namely subtyping in connection with object-oriented programming and overloading. While subtyping is incompatible with HM, a variant of systematic overloading is available in the HM-based type system of Haskell. === Let-polymorphism === When extending the type inference for the simply-typed lambda calculus towards polymorphism, one has to decide whether assigning a polymorphic type not only as type of an expression, but also as the type of a λ-bound variable is admissible. This would allow the generic identity type to be assigned to the variable 'id' in: (λ id . ... (id 3) ... (id "text") ... ) (λ x . x) Allowing this gives rise to the polymorphic lambda calculus; however, type inference in this system is not decidable. Instead, HM distinguishes variables that are immediately bound to an expression from more general λ-bound variables, calling the former let-bound variables, and allows polymorphic types to be assigned only to these. This leads to let-polymorphism where the above example takes the form let id = λ x . x in ... (id 3) ... (id "text") ... which can be typed with a polymorphic type for 'id'. As indicated, the expression syntax is extended to make the let-bound variables explicit, and by restricting the type system to allow only let-bound variable to have polymorphic types, while the parameters in lambda-abstractions must get a monomorphic type, type inference becomes decidable. == Overview == The remainder of this article proceeds as follows: The HM type system is defined. This is done by describing a deduction system that makes precise what expressions have what type, if any. From there, it works towards an implementation of the type inference method. After introducing a syntax-driven variant of the above deductive system, it sketches an efficient implementation (algorithm J), appealing mostly to the reader's metalogical intuition. Because it remains open whether algorithm J indeed realises the initial deduction system, a less efficient implementation (algorithm W), is introduced and its use in a proof is hinted. Finally, further topics related to the algorithm are discussed. The same description of the deduction system is used throughout, even for the two algorithms, to make the various forms in which the HM method is presented directly comparable. == The Hindley–Milner type system == The type system can be formally described by syntax rules that fix a language for the expressions, types, etc. The presentation here of such a syntax is not too formal, in that it is written down not to study the surface grammar, but rather the depth grammar, and leaves some syntactical details open. This form of presentation is usual. Building on this, typing rules are used to define how expressions and types are related. As before, the form used is a bit liberal. === Syntax === The expressions to be typed are exactly those of the lambda calculus extended with a let-expression as shown in the adjacent table. Parentheses can be used to disambiguate an expression. The application is left-binding and binds stronger than abstraction or the let-in construct. Types are syntactically split into two groups, monotypes and polytypes. ==== Monotypes ==== Monotypes always designate a particular type. Monotypes τ {\displaystyle \tau } are syntactically represented as terms. Examples of monotypes include type constants like i n t {\displaystyle {\mathtt {int}}} or s t r i n g {\displaystyle {\mathtt {string}}} , and parametric types like M a p ( S e t s t r i n g ) i n t {\displaystyle {\mathtt {Map\ (Set\ string)\ int}}} . The latter types are examples of applications of type functions, for example, from the set { M a p 2 , S e t 1 , s t r i n g 0 , i n t 0 , → 2 } {\displaystyle \{{\mathtt {Map^{2},\ Set^{1},\ string^{0},\ int^{0}}},\ \rightarrow ^{2}\}} , where the superscript indicates the number of type parameters. The complete set of type functions C {\displaystyle C} is arbitrary in HM, except that it must contain at least → 2 {\displaystyle \rightarrow ^{2}} , the type of functions. It is often written in infix notation for convenience. For example, a function mapping integers to strings has type i n t → s t r i n g {\displaystyle {\mathtt {int}}\rightarrow {\mathtt {string}}} . Again, parentheses can be used to disambiguate a type expression. The application binds stronger than the infix arrow, which is right-binding. Type variables are admitted as monotypes. Monotypes are not to be confused with monomorphic types, which exc