In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1957 (Nerode & Sauer 1957, p. ii). == Statement == Given a language L {\displaystyle L} , and a pair of strings x {\displaystyle x} and y {\displaystyle y} , define a distinguishing extension to be a string z {\displaystyle z} such that exactly one of the two strings x z {\displaystyle xz} and y z {\displaystyle yz} belongs to L {\displaystyle L} . Define a relation ∼ L {\displaystyle \sim _{L}} on strings as x ∼ L y {\displaystyle x\;\sim _{L}\ y} if there is no distinguishing extension for x {\displaystyle x} and y {\displaystyle y} . It is easy to show that ∼ L {\displaystyle \sim _{L}} is an equivalence relation on strings, and thus it divides the set of all strings into equivalence classes. The Myhill–Nerode theorem states that a language L {\displaystyle L} is regular if and only if ∼ L {\displaystyle \sim _{L}} has a finite number of equivalence classes, and moreover, that this number is equal to the number of states in the minimal deterministic finite automaton (DFA) accepting L {\displaystyle L} . Furthermore, every minimal DFA for the language is isomorphic to the canonical one (Hopcroft & Ullman 1979). Generally, for any language, the constructed automaton is a state automaton acceptor. However, it does not necessarily have finitely many states. The Myhill–Nerode theorem shows that finiteness is necessary and sufficient for language regularity. Some authors refer to the ∼ L {\displaystyle \sim _{L}} relation as Nerode congruence, in honor of Anil Nerode. == Use and consequences == The Myhill–Nerode theorem may be used to show that a language L {\displaystyle L} is regular by proving that the number of equivalence classes of ∼ L {\displaystyle \sim _{L}} is finite. This may be done by an exhaustive case analysis in which, beginning from the empty string, distinguishing extensions are used to find additional equivalence classes until no more can be found. For example, the language consisting of binary representations of numbers that can be divided by 3 is regular. Given two binary strings x , y {\displaystyle x,y} , extending them by one digit gives 2 x + b , 2 y + b {\displaystyle 2x+b,2y+b} , so 2 x + b ≡ 2 y + b mod 3 {\displaystyle 2x+b\equiv 2y+b\mod 3} iff x ≡ y mod 3 {\displaystyle x\equiv y\mod 3} . Thus, 00 {\displaystyle 00} (or 11 {\displaystyle 11} ), 01 {\displaystyle 01} , and 10 {\displaystyle 10} are the only distinguishing extensions, resulting in the 3 classes. The minimal automaton accepting our language would have three states corresponding to these three equivalence classes. Another immediate corollary of the theorem is that if for a language L {\displaystyle L} the relation ∼ L {\displaystyle \sim _{L}} has infinitely many equivalence classes, it is not regular. It is this corollary that is frequently used to prove that a language is not regular. == Generalizations == The Myhill–Nerode theorem can be generalized to tree automata.
Probiv
Probiv (Russian: пробив, literally "to pierce" or "to punch through") is an illicit data market operating primarily in Russia, where personal information from restricted government and corporate databases is bought and sold through networks of corrupt officials and insiders. The probiv market operates as a parallel information economy built on corrupt officials from various sectors including traffic police, banks, telecommunications companies, and security services who sell access to restricted databases. For fees ranging from as little as $10 to several hundred dollars, buyers can obtain passport numbers, addresses, travel histories, vehicle registrations, and telecommunications records. The market operates through various channels, including specialized Telegram bots and darknet forums. == Notable uses == Probiv services have been utilized by diverse actors for various purposes. Investigative journalists have used the market to conduct high-profile investigations, including tracing the FSB unit allegedly behind the poisoning of Alexei Navalny. Russian police and security services themselves have routinely used the black market to track activists and opposition figures. Since Russia's invasion of Ukraine, Ukrainian intelligence services have exploited the market to identify Russian military officials. == Government response == In late 2024, Russian authorities introduced legislation imposing penalties of up to ten years in prison for accessing or distributing leaked data. Several operators of probiv services, including the teams behind Usersbox and Solaris, have been arrested. However, the crackdown appears to have had unintended consequences. Many operators have relocated their businesses abroad, where they operate with fewer constraints. Some services that previously cooperated with Russian authorities have severed those ties and moved staff out of the country.
SmarterChild
SmarterChild was a chatbot available on AOL Instant Messenger and Windows Live Messenger (previously MSN Messenger) networks. == History == SmarterChild was an apparently intelligent agent or "bot" developed by ActiveBuddy, Inc., with offices in New York and Sunnyvale. It was widely distributed across global instant messaging networks. SmarterChild became very popular, attracting over 30 million Instant Messenger "buddies" on AIM (AOL), MSN and Yahoo Messenger over the course of its lifetime. Founded in 2000, ActiveBuddy was the brainchild of Robert Hoffer and Timothy Kay, who later brought seasoned advertising executive Peter Levitan on board as CEO. The concept for conversational instant messaging bots came from the founder's vision to add natural language comprehension functionality to the increasingly popular AIM instant messaging application. The original implementation took shape as a demo that Kay programmed in Perl in his Los Altos garage to connect a single buddy name, "ActiveBuddy", to look up stock symbols, and later allow AIM users to play Colossal Cave Adventure, a word-based adventure game, and MIT's Boris Katz Start Question Answering System but quickly grew to include a wide range of database applications the company called 'knowledge domains' including instant access to news, weather, stock information, movie times, yellow pages listings, and detailed sports data, as well as a variety of tools (personal assistant, calculators, translator, etc.). None of the individual domains which the company had named “stocksBuddy”, “sportsBuddy”, etc. ever launched publicly. When Stephen Klein came on board as COO — and eventually CEO — he insisted that all of the disparate test “buddies” be launched together with the company’s highly-developed colloquial chat domain. He suggested using “SmarterChild”, a username coined by Tim Kay which Tim was using to test various things. The bundled domains were launched publicly as SmarterChild (on AIM initially) in June 2001. SmarterChild provided information wrapped in fun and quirky conversation. The company generated no revenue from SmarterChild, but used it as a demonstration of the power of what Klein called “conversational computing”. The company subsequently marketed Automated Service Agents—delivering immediate answers to customer service inquiries—-to large corporations, like Comcast, Cingular, TimeWarner Cable, etc. SmarterChild's popularity spawned targeted marketing-oriented bots for Radiohead, Austin Powers, Intel, Keebler, The Sporting News and others. ActiveBuddy co-founders, Kay and Hoffer, as co-inventors, were issued two controversial U.S. patents in 2002. ActiveBuddy changed its name to Colloquis (briefly Conversagent) and targeted development of consumer-facing enterprise customer service agents, which the company marketed as Automated Service Agents. Microsoft acquired Colloquis in October 2006 and proceeded to de-commission SmarterChild and kill off the Automated Service Agent business as well. Robert Hoffer, ActiveBuddy co-founder, licensed the technology from Microsoft after Microsoft abandoned the Colloquis technology.
Ed (chatbot)
Ed was a chatbot co-developed by the Los Angeles Unified School District and AllHere Education. Described as a learning acceleration platform, it was the first personal assistant for students in the United States. Part of the district's Individual Acceleration Plan, it was able to interact with students both verbally and visually, offering support in 100 languages. The chatbot was launched on March 20, 2024, as part of the district's plan for academic recovery from the COVID-19 pandemic and to improve overall academic performance. Utilizing artificial intelligence, Ed organizes data and reports on grades, test scores, and attendance, creating individualized plans for each student. After the company behind it, AllHere, collapsed, the district shuttered operations of the chatbot on June 14, 2024. The firm is under investigation by the US Federal Bureau of Investigation. == History == On February 14, 2022, Alberto M. Carvalho became the Superintendent of the Los Angeles Unified School District, pledging to give the district a full academic recovery from the COVID-19 pandemic. In December 2022, he announced the Individual Acceleration Plan for the district, which aimed to provide each student with a unique progress report and help them determine if they were on track to graduate. The district faced criticism from disability advocates for its management of Individualized Education Programs, and in April 2022, the United States Department of Education announced that the district had failed to provide appropriate educational services to students with disabilities during the pandemic. The district had been grappling with significant absenteeism issues since the pandemic, which led to declining academic performance and disengagement among students. On February 17, 2023, the district issued a request for proposals to develop a fully integrated portal system. Later that year, they signed a $6 million, five-year contract with AllHere Education, a Boston-based company founded in 2016. The introduction of Ed follows the public launch of ChatGPT, which has been utilized by both teachers and students in educational settings. On August 4, 2023, during an annual address at the Walt Disney Concert Hall, Carvalho and the Los Angeles Unified School District announced the launch of Ed. The district invested $4 million into the chatbot, with Carvalho noting that this cost would be halved thanks to donor and grant funding. The chatbot was launched on March 20, 2024. Following its launch, a press conference was held to address security and technology concerns. Carvalho stated that the district had collaborated with security companies and incorporated filters to screen for threatening language. Months after its launch, AllHere Education furloughed most of its staff on June 14, citing their “current financial position” on its website as the reason. After learning about the furlough, the district terminated its dealings with AllHere Education. However, it stated its intention to bring the chatbot back in the future once officials determine the best course of action. Carvalho announced that he would appoint an independent task force to review what went wrong with AllHere Education and the chatbot. On February 25, 2026, the FBI served a search warrant on Carvalho’s home and office in connection with AllHere. The FBI also raided the LAUSD's headquarters. == Service == The chatbot was described as a personal assistant and a "one-stop shop for parents and students" who want to see information about a student's attendance and grades, as well as other resources from the district. Additionally, the application can function as an alarm clock, provide daily lunch menus from the school cafeteria, and offer updates on the location of school buses. The chatbot also helps students and parents who do not speak English as their first language by translating displayed information into approximately 100 different languages. The application can also help with submitting applications and give updates on progress and upcoming assignments. The district stated that the primary goal of Ed was to actively motivate students to complete homework and other tasks. == Reception == The chatbot received a mostly positive reception among parents and observers upon its launch. Some parents and teachers expressed caution about the technology, voicing concerns that the district's push for its implementation lacked public accountability. Rob Nelson from the University of Pennsylvania described the district's strategy as risky, saying that the release felt "like the beginning of a Clippy-level disaster". After the chatbot's shutdown, The 74 criticized it for misusing student data. Chris Whiteley, a former software engineer at AllHere Education, alleged that the data collected by the chatbot likely violated the district's data privacy rules.
N-jet
An N-jet is the set of (partial) derivatives of a function f ( x ) {\displaystyle f(x)} up to order N. Specifically, in the area of computer vision, the N-jet is usually computed from a scale space representation L {\displaystyle L} of the input image f ( x , y ) {\displaystyle f(x,y)} , and the partial derivatives of L {\displaystyle L} are used as a basis for expressing various types of visual modules. For example, algorithms for tasks such as feature detection, feature classification, stereo matching, tracking and object recognition can be expressed in terms of N-jets computed at one or several scales in scale space.
Geometric primitive
In vector computer graphics, CAD systems, and geographic information systems, a geometric primitive (or prim) is the simplest (i.e. 'atomic' or irreducible) geometric shape that the system can handle (draw, store). Sometimes the subroutines that draw the corresponding objects are called "geometric primitives" as well. The most "primitive" primitives are point and straight line segments, which were all that early vector graphics systems had. In constructive solid geometry, primitives are simple geometric shapes such as a cube, cylinder, sphere, cone, pyramid, torus. Modern 2D computer graphics systems may operate with primitives which are curves (segments of straight lines, circles and more complicated curves), as well as shapes (boxes, arbitrary polygons, circles). A common set of two-dimensional primitives includes lines, points, and polygons, although some people prefer to consider triangles primitives, because every polygon can be constructed from triangles (polygon triangulation). All other graphic elements are built up from these primitives. In three dimensions, triangles or polygons positioned in three-dimensional space can be used as primitives to model more complex 3D forms. In some cases, curves (such as Bézier curves, circles, etc.) may be considered primitives; in other cases, curves are complex forms created from many straight, primitive shapes. == Common primitives == The set of geometric primitives is based on the dimension of the region being represented: Point (0-dimensional), a single location with no height, width, or depth. Line or curve (1-dimensional), having length but no width, although a linear feature may curve through a higher-dimensional space. Planar surface or curved surface (2-dimensional), having length and width. Volumetric region or solid (3-dimensional), having length, width, and depth. In GIS, the terrain surface is often spoken of colloquially as "2 1/2 dimensional," because only the upper surface needs to be represented. Thus, elevation can be conceptualized as a scalar field property or function of two-dimensional space, affording it a number of data modeling efficiencies over true 3-dimensional objects. A shape of any of these dimensions greater than zero consists of an infinite number of distinct points. Because digital systems are finite, only a sample set of the points in a shape can be stored. Thus, vector data structures typically represent geometric primitives using a strategic sample, organized in structures that facilitate the software interpolating the remainder of the shape at the time of analysis or display, using the algorithms of Computational geometry. A Point is a single coordinate in a Cartesian coordinate system. Some data models allow for Multipoint features consisting of several disconnected points. A Polygonal chain or Polyline is an ordered list of points (termed vertices in this context). The software is expected to interpolate the intervening shape of the line between adjacent points in the list as a parametric curve, most commonly a straight line, but other types of curves are frequently available, including circular arcs, cubic splines, and Bézier curves. Some of these curves require additional points to be defined that are not on the line itself, but are used for parametric control. A Polygon is a polyline that closes at its endpoints, representing the boundary of a two-dimensional region. The software is expected to use this boundary to partition 2-dimensional space into an interior and exterior. Some data models allow for a single feature to consist of multiple polylines, which could collectively connect to form a single closed boundary, could represent a set of disjoint regions (e.g., the state of Hawaii), or could represent a region with holes (e.g., a lake with an island). A Parametric shape is a standardized two-dimensional or three-dimensional shape defined by a minimal set of parameters, such as an ellipse defined by two points at its foci, or three points at its center, vertex, and co-vertex. A Polyhedron or Polygon mesh is a set of polygon faces in three-dimensional space that are connected at their edges to completely enclose a volumetric region. In some applications, closure may not be required or may be implied, such as modeling terrain. The software is expected to use this surface to partition 3-dimensional space into an interior and exterior. A triangle mesh is a subtype of polyhedron in which all faces must be triangles, the only polygon that will always be planar, including the Triangulated irregular network (TIN) commonly used in GIS. A parametric mesh represents a three-dimensional surface by a connected set of parametric functions, similar to a spline or Bézier curve in two dimensions. The most common structure is the Non-uniform rational B-spline (NURBS), supported by most CAD and animation software. == Application in GIS == A wide variety of vector data structures and formats have been developed during the history of Geographic information systems, but they share a fundamental basis of storing a core set of geometric primitives to represent the location and extent of geographic phenomena. Locations of points are almost always measured within a standard Earth-based coordinate system, whether the spherical Geographic coordinate system (latitude/longitude), or a planar coordinate system, such as the Universal Transverse Mercator. They also share the need to store a set of attributes of each geographic feature alongside its shape; traditionally, this has been accomplished using the data models, data formats, and even software of relational databases. Early vector formats, such as POLYVRT, the ARC/INFO Coverage, and the Esri shapefile support a basic set of geometric primitives: points, polylines, and polygons, only in two dimensional space and the latter two with only straight line interpolation. TIN data structures for representing terrain surfaces as triangle meshes were also added. Since the mid 1990s, new formats have been developed that extend the range of available primitives, generally standardized by the Open Geospatial Consortium's Simple Features specification. Common geometric primitive extensions include: three-dimensional coordinates for points, lines, and polygons; a fourth "dimension" to represent a measured attribute or time; curved segments in lines and polygons; text annotation as a form of geometry; and polygon meshes for three-dimensional objects. Frequently, a representation of the shape of a real-world phenomenon may have a different (usually lower) dimension than the phenomenon being represented. For example, a city (a two-dimensional region) may be represented as a point, or a road (a three-dimensional volume of material) may be represented as a line. This dimensional generalization correlates with tendencies in spatial cognition. For example, asking the distance between two cities presumes a conceptual model of the cities as points, while giving directions involving travel "up," "down," or "along" a road imply a one-dimensional conceptual model. This is frequently done for purposes of data efficiency, visual simplicity, or cognitive efficiency, and is acceptable if the distinction between the representation and the represented is understood, but can cause confusion if information users assume that the digital shape is a perfect representation of reality (i.e., believing that roads really are lines). == In 3D modelling == In CAD software or 3D modelling, the interface may present the user with the ability to create primitives which may be further modified by edits. For example, in the practice of box modelling the user will start with a cuboid, then use extrusion and other operations to create the model. In this use the primitive is just a convenient starting point, rather than the fundamental unit of modelling. A 3D package may also include a list of extended primitives which are more complex shapes that come with the package. For example, a teapot is listed as a primitive in 3D Studio Max. == In graphics hardware == Various graphics accelerators exist with hardware acceleration for rendering specific primitives such as lines or triangles, frequently with texture mapping and shaders. Modern 3D accelerators typically accept sequences of triangles as triangle strips.
List of large language models
A large language model (LLM) is a type of machine learning model designed for natural language processing tasks such as language generation. LLMs are language models with many parameters, and are trained with self-supervised learning on a vast amount of text. == List == For the training cost column, 1 petaFLOP-day equals 1 petaFLOP/sec × 1 day, or 8.64×1019 FLOP (floating point operations). Only the cost of the largest model is shown. The number of parameters is measured in billions, and the training cost is measured in petaFLOP-days. === 2018 === === 2019 === === 2020 === === 2021 === === 2022 === === 2023 === === 2024 === === 2025 === === 2026 ===