In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. This is in contrast to a Moore machine, whose output values are determined solely by its current state. A Mealy machine is a deterministic finite-state transducer: for each state and input, at most one transition is possible. == History == The Mealy machine is named after George H. Mealy, who presented the concept in a 1955 paper, "A Method for Synthesizing Sequential Circuits". == Formal definition == A Mealy machine is a 6-tuple ( S , S 0 , Σ , Λ , T , G ) {\displaystyle (S,S_{0},\Sigma ,\Lambda ,T,G)} consisting of the following: a finite set of states S {\displaystyle S} a start state (also called initial state) S 0 {\displaystyle S_{0}} which is an element of S {\displaystyle S} a finite set called the input alphabet Σ {\displaystyle \Sigma } a finite set called the output alphabet Λ {\displaystyle \Lambda } a transition function T : S × Σ → S {\displaystyle T:S\times \Sigma \rightarrow S} mapping pairs of a state and an input symbol to the corresponding next state. an output function G : S × Σ → Λ {\displaystyle G:S\times \Sigma \rightarrow \Lambda } mapping pairs of a state and an input symbol to the corresponding output symbol. In some formulations, the transition and output functions are coalesced into a single function T : S × Σ → S × Λ {\displaystyle T:S\times \Sigma \rightarrow S\times \Lambda } . "Evolution across time" is realized in this abstraction by having the state machine consult the time-changing input symbol at discrete "timer ticks" t 0 , t 1 , t 2 , . . . {\displaystyle t_{0},t_{1},t_{2},...} and react according to its internal configuration at those idealized instants, or else having the state machine wait for a next input symbol (as on a FIFO) and react whenever it arrives. == Comparison of Mealy machines and Moore machines == Mealy machines tend to have fewer states: Different outputs on arcs (n2) rather than states (n). When implemented as electronic circuits (rather than as mathematical abstractions or code): Moore machines are safer to use than Mealy machines: Outputs change at the clock edge (always one cycle later). In Mealy machines, input change can cause output change as soon as logic is done — a big problem when two machines are interconnected – asynchronous feedback may occur if one isn't careful. Mealy machines react faster to inputs: React in the same cycle—they don't need to wait for the clock. In Moore machines, more logic may be necessary to decode state into outputs—more gate delays after clock edge. == Diagram == The state diagram for a Mealy machine associates an output value with each transition edge, in contrast to the state diagram for a Moore machine, which associates an output value with each state. When the input and output alphabet are both Σ, one can also associate to a Mealy automata a Helix directed graph (S × Σ, (x, i) → (T(x, i), G(x, i))). This graph has as vertices the couples of state and letters, each node is of out-degree one, and the successor of (x, i) is the next state of the automata and the letter that the automata output when it is instate x and it reads letter i. This graph is a union of disjoint cycles if the automaton is bireversible. == Examples == === Simple === A simple Mealy machine has one input and one output. Each transition edge is labeled with the value of the input (shown in red) and the value of the output (shown in blue). The machine starts in state Si. (In this example, the output is the exclusive-or of the two most-recent input values; thus, the machine implements an edge detector, outputting a 1 every time the input flips and a 0 otherwise.) === Complex === More complex Mealy machines can have multiple inputs as well as multiple outputs. == Applications == Mealy machines provide a rudimentary mathematical model for cipher machines. Considering the input and output alphabet the Latin alphabet, for example, then a Mealy machine can be designed that given a string of letters (a sequence of inputs) can process it into a ciphered string (a sequence of outputs). However, although a Mealy model could be used to describe the Enigma, the state diagram would be too complex to provide feasible means of designing complex ciphering machines. Moore/Mealy machines are DFAs that have also output at any tick of the clock. Modern CPUs, computers, cell phones, digital clocks and basic electronic devices/machines have some kind of finite state machine to control it. Simple software systems, particularly ones that can be represented using regular expressions, can be modeled as finite state machines. There are many such simple systems, such as vending machines or basic electronics. By finding the intersection of two finite state machines, one can design in a very simple manner concurrent systems that exchange messages for instance. For example, a traffic light is a system that consists of multiple subsystems, such as the different traffic lights, that work concurrently.
Line Drawing System-1
LDS-1 (Line Drawing System-1) was a calligraphic (vector, rather than raster) display processor and display device created by Evans & Sutherland in 1969. This model was known as the first graphics device with a graphics processing unit. == Features == It was controlled by a variety of host computers. Straight lines were smoothly rendered in real-time animation. General principles of operation were similar to the systems used today: 4x4 transformation matrices, 1x4 vertices. Possible uses included flight simulation (in the product brochure there are screenshots of landing on a carrier), scientific imaging and GIS systems. == History == The first LDS-1 was shipped to the customer (BBN) in August 1969. Only a few of these systems were ever built. One was used by the Los Angeles Times as their first typesetting/layout computer. One went to NASA Ames Research Center for Human Factors Research. Another was bought by the Port Authority of New York to develop a tugboat pilot trainer for navigation in the harbor. The MIT Dynamic Modeling had one, and there was a program for viewing an ongoing game of Maze War.
Cozi
Cozi is a family organization website and mobile app designed to streamline household management. It offers shared calendars, to-do lists, shopping lists, and messaging tools, allowing multiple users to coordinate under one account. Founded in 2005 by former Microsoft employees, Cozi has evolved through acquisitions and now operates under OurFamilyWizard. The app is available in both free and premium versions on iOS, Android, and desktop platforms. == History == Cozi was founded in 2005 by Robbie Cape and Jan Miksovsky, two former Microsoft employees who sought to simplify family logistics with technology. The company's first product, Cozi Central, was released on September 25, 2006, and included a family calendar, shopping lists, family messaging and a photo collage screensaver. The company is based in Seattle, Washington. Cozi has both a freemium version, and a paid version called Cozi Gold. Cozi Gold's additional features include Cozi Contacts, a birthday tracker, more reminders, mobile month view, and change notifications. The software can be used on desktop or mobile applications for iOS and Android. On June 5, 2011, Cozi set a Guinness World Record for the longest line of ducks in a row. The line stretched for one mile and was made up of 17,782 rubber ducks. Cozi was acquired by Time Inc. in 2014. After the Meredith Corporation acquired Time in 2018, Cozi was moved into the Parents Network division. On May 4, 2022, Cozi was acquired by OurFamilyWizard of Minneapolis, Minnesota, reporting more than 20 million registered users.
Read the Docs
Read the Docs is an open-sourced free software documentation hosting platform. It generates documentation written with the Sphinx documentation generator, MkDocs, or Jupyter Book. == History == The site was created in 2010 by Eric Holscher, Bobby Grace, and Charles Leifer. On March 9, 2011, the Python Software Foundation Board awarded a grant of US$840 to the Read the Docs project for one year of hosting fees. On November 13, 2017, the Linux Mint project announced that they were moving their documentation to Read the Docs. In 2020, Read the Docs received a $200,000 grant from the Chan Zuckerberg Initiative. For 2021, Read the Docs reported 700 million page views and 196 million unique visitors. In 2013, a "Write the Docs" conference for Read the Docs users was launched, which has since turned into a generic software-documentation community. As of 2024, it continues to hold annual global conferences, organize local meetups, and maintain a Slack channel for "people who care about documentation."
Plant Nanny
Plant Nanny is a water tracker mobile application which reminds users to drink water. It was developed by Taiwanese app maker Fourdesire. The app was first released in 2013 and is available on the Apple App Store for iPhones and the Google Play Store for Android devices. == Description == Play Nanny uses a game method that allows users to turn their virtual selves into plants, which grows and thrives as the user drinks more water. The app sends occasional push notifications to remind users to drink water throughout the day. Users can choose from a wide range of plants, including cacti and carnations, and track their water intake. The app uses two resources, How to calculate how much water you should drink by Jennifer Stone (2018) and Human energy requirements by the Food and Agriculture Organization (2004), to calculate the recommended daily water intake for its users. Upon downloading the app, users are prompted to input basic personal information which is then used to calculate the recommended daily water intake and prompts them to drink the appropriate amount. == Accolades ==
Coupled pattern learner
Coupled Pattern Learner (CPL) is a machine learning algorithm which couples the semi-supervised learning of categories and relations to forestall the problem of semantic drift associated with boot-strap learning methods. == Coupled Pattern Learner == Semi-supervised learning approaches using a small number of labeled examples with many unlabeled examples are usually unreliable as they produce an internally consistent, but incorrect set of extractions. CPL solves this problem by simultaneously learning classifiers for many different categories and relations in the presence of an ontology defining constraints that couple the training of these classifiers. It was introduced by Andrew Carlson, Justin Betteridge, Estevam R. Hruschka Jr. and Tom M. Mitchell in 2009. == CPL overview == CPL is an approach to semi-supervised learning that yields more accurate results by coupling the training of many information extractors. Basic idea behind CPL is that semi-supervised training of a single type of extractor such as ‘coach’ is much more difficult than simultaneously training many extractors that cover a variety of inter-related entity and relation types. Using prior knowledge about the relationships between these different entities and relations CPL makes unlabeled data as a useful constraint during training. For e.g., ‘coach(x)’ implies ‘person(x)’ and ‘not sport(x)’. == CPL description == === Coupling of predicates === CPL primarily relies on the notion of coupling the learning of multiple functions so as to constrain the semi-supervised learning problem. CPL constrains the learned function in two ways. Sharing among same-arity predicates according to logical relations Relation argument type-checking === Sharing among same-arity predicates === Each predicate P in the ontology has a list of other same-arity predicates with which P is mutually exclusive. If A is mutually exclusive with predicate B, A’s positive instances and patterns become negative instances and negative patterns for B. For example, if ‘city’, having an instance ‘Boston’ and a pattern ‘mayor of arg1’, is mutually exclusive with ‘scientist’, then ‘Boston’ and ‘mayor of arg1’ will become a negative instance and a negative pattern respectively for ‘scientist.’ Further, Some categories are declared to be a subset of another category. For e.g., ‘athlete’ is a subset of ‘person’. === Relation argument type-checking === This is a type checking information used to couple the learning of relations and categories. For example, the arguments of the ‘ceoOf’ relation are declared to be of the categories ‘person’ and ‘company’. CPL does not promote a pair of noun phrases as an instance of a relation unless the two noun phrases are classified as belonging to the correct argument types. === Algorithm description === Following is a quick summary of the CPL algorithm. Input: An ontology O, and a text corpus C Output: Trusted instances/patterns for each predicate for i=1,2,...,∞ do foreach predicate p in O do EXTRACT candidate instances/contextual patterns using recently promoted patterns/instances; FILTER candidates that violate coupling; RANK candidate instances/patterns; PROMOTE top candidates; end end ==== Inputs ==== A large corpus of Part-Of-Speech tagged sentences and an initial ontology with predefined categories, relations, mutually exclusive relationships between same-arity predicates, subset relationships between some categories, seed instances for all predicates, and seed patterns for the categories. ==== Candidate extraction ==== CPL finds new candidate instances by using newly promoted patterns to extract the noun phrases that co-occur with those patterns in the text corpus. CPL extracts, Category Instances Category Patterns Relation Instances Relation Patterns ==== Candidate filtering ==== Candidate instances and patterns are filtered to maintain high precision, and to avoid extremely specific patterns. An instance is only considered for assessment if it co-occurs with at least two promoted patterns in the text corpus, and if its co-occurrence count with all promoted patterns is at least three times greater than its co-occurrence count with negative patterns. ==== Candidate ranking ==== CPL ranks candidate instances using the number of promoted patterns that they co-occur with so that candidates that occur with more patterns are ranked higher. Patterns are ranked using an estimate of the precision of each pattern. ==== Candidate promotion ==== CPL ranks the candidates according to their assessment scores and promotes at most 100 instances and 5 patterns for each predicate. Instances and patterns are only promoted if they co-occur with at least two promoted patterns or instances, respectively. == Meta-Bootstrap Learner == Meta-Bootstrap Learner (MBL) was also proposed by the authors of CPL. Meta-Bootstrap learner couples the training of multiple extraction techniques with a multi-view constraint, which requires the extractors to agree. It makes addition of coupling constraints on top of existing extraction algorithms, while treating them as black boxes, feasible. MBL assumes that the errors made by different extraction techniques are independent. Following is a quick summary of MBL. Input: An ontology O, a set of extractors ε Output: Trusted instances for each predicate for i=1,2,...,∞ do foreach predicate p in O do foreach extractor e in ε do Extract new candidates for p using e with recently promoted instances; end FILTER candidates that violate mutual-exclusion or type-checking constraints; PROMOTE candidates that were extracted by all extractors; end end Subordinate algorithms used with MBL do not promote any instance on their own, they report the evidence about each candidate to MBL and MBL is responsible for promoting instances. == Applications == In their paper authors have presented results showing the potential of CPL to contribute new facts to existing repository of semantic knowledge, Freebase
Digital image correlation and tracking
Digital image correlation and tracking is an optical method that employs tracking and image registration techniques for accurate 2D and 3D measurements of changes in 2D images or 3D volumes. This method is often used to measure full-field displacement and strains, and it is widely applied in many areas of science and engineering. Compared to strain gauges and extensometers, digital image correlation methods provide finer details about deformation, due to the ability to provide both local and average data. == Overview == Digital image correlation (DIC) techniques have been increasing in popularity, especially in micro- and nano-scale mechanical testing applications due to their relative ease of implementation and use. Advances in computer technology and digital cameras have been the enabling technologies for this method and while white-light optics has been the predominant approach, DIC can be and has been extended to almost any imaging technology. The concept of using cross-correlation to measure shifts in datasets has been known for a long time, and it has been applied to digital images since at least the early 1970s. The present-day applications are almost innumerable, including image analysis, image compression, velocimetry, and strain estimation. Much early work in DIC in the field of mechanics was led by researchers at the University of South Carolina in the early 1980s and has been optimized and improved in recent years. Commonly, DIC relies on finding the maximum of the correlation array between pixel intensity array subsets on two or more corresponding images, which gives the integer translational shift between them. It is also possible to estimate shifts to a finer resolution than the resolution of the original images, which is often called "sub-pixel" registration because the measured shift is smaller than an integer pixel unit. For sub-pixel interpolation of the shift, other methods do not simply maximize the correlation coefficient. An iterative approach can also be used to maximize the interpolated correlation coefficient by using non-linear optimization techniques. The non-linear optimization approach tends to be conceptually simpler and can handle large deformations more accurately, but as with most nonlinear optimization techniques, it is slower. The two-dimensional discrete cross correlation r i j {\displaystyle r_{ij}} can be defined in several ways, one possibility being: r i j = ∑ m ∑ n [ f ( m + i , n + j ) − f ¯ ] [ g ( m , n ) − g ¯ ] ∑ m ∑ n [ f ( m , n ) − f ¯ ] 2 ∑ m ∑ n [ g ( m , n ) − g ¯ ] 2 . {\displaystyle r_{ij}={\frac {\sum _{m}\sum _{n}[f(m+i,n+j)-{\bar {f}}][g(m,n)-{\bar {g}}]}{\sqrt {\sum _{m}\sum _{n}{[f(m,n)-{\bar {f}}]^{2}}\sum _{m}\sum _{n}{[g(m,n)-{\bar {g}}]^{2}}}}}.} Here f(m, n) is the pixel intensity or the gray-scale value at a point (m, n) in the original image, g(m, n) is the gray-scale value at a point (m, n) in the translated image, f ¯ {\displaystyle {\bar {f}}} and g ¯ {\displaystyle {\bar {g}}} are mean values of the intensity matrices f and g respectively. However, in practical applications, the correlation array is usually computed using Fourier-transform methods, since the fast Fourier transform is a much faster method than directly computing the correlation. F = F { f } , G = F { g } . {\displaystyle \mathbf {F} ={\mathcal {F}}\{f\},\quad \mathbf {G} ={\mathcal {F}}\{g\}.} Then taking the complex conjugate of the second result and multiplying the Fourier transforms together elementwise, we obtain the Fourier transform of the correlogram, R {\displaystyle \ R} : R = F ∘ G ∗ , {\displaystyle R=\mathbf {F} \circ \mathbf {G} ^{},} where ∘ {\displaystyle \circ } is the Hadamard product (entry-wise product). It is also fairly common to normalize the magnitudes to unity at this point, which results in a variation called phase correlation. Then the cross-correlation is obtained by applying the inverse Fourier transform: r = F − 1 { R } . {\displaystyle \ r={\mathcal {F}}^{-1}\{R\}.} At this point, the coordinates of the maximum of r i j {\displaystyle r_{ij}} give the integer shift: ( Δ x , Δ y ) = arg max ( i , j ) { r } . {\displaystyle (\Delta x,\Delta y)=\arg \max _{(i,j)}\{r\}.} == Deformation mapping == For deformation mapping, the mapping function that relates the images can be derived from comparing a set of subwindow pairs over the whole images. (Figure 1). The coordinates or grid points (xi, yj) and (xi, yj) are related by the translations that occur between the two images. If the deformation is small and perpendicular to the optical axis of the camera, then the relation between (xi, yj) and (xi, yj) can be approximated by a 2D affine transformation such as: x ∗ = x + u + ∂ u ∂ x Δ x + ∂ u ∂ y Δ y , {\displaystyle x^{}=x+u+{\frac {\partial u}{\partial x}}\Delta x+{\frac {\partial u}{\partial y}}\Delta y,} y ∗ = y + v + ∂ v ∂ x Δ x + ∂ v ∂ y Δ y . {\displaystyle y^{}=y+v+{\frac {\partial v}{\partial x}}\Delta x+{\frac {\partial v}{\partial y}}\Delta y.} Here u and v are translations of the center of the sub-image in the X and Y directions respectively. The distances from the center of the sub-image to the point (x, y) are denoted by Δ x {\displaystyle \Delta x} and Δ y {\displaystyle \Delta y} . Thus, the correlation coefficient rij is a function of displacement components (u, v) and displacement gradients ∂ u ∂ x , ∂ u ∂ y , ∂ v ∂ x , ∂ v ∂ y . {\displaystyle {\frac {\partial u}{\partial x}},{\frac {\partial u}{\partial y}},{\frac {\partial v}{\partial x}},{\frac {\partial v}{\partial y}}.} DIC has proven to be very effective at mapping deformation in macroscopic mechanical testing, where the application of specular markers (e.g. paint, toner powder) or surface finishes from machining and polishing provide the needed contrast to correlate images well. However, these methods for applying surface contrast do not extend to the application of free-standing thin films for several reasons. First, vapor deposition at normal temperatures on semiconductor grade substrates results in mirror-finish quality films with RMS roughnesses that are typically on the order of several nanometers. No subsequent polishing or finishing steps are required, and unless electron imaging techniques are employed that can resolve microstructural features, the films do not possess enough useful surface contrast to adequately correlate images. Typically this challenge can be circumvented by applying paint that results in a random speckle pattern on the surface, although the large and turbulent forces resulting from either spraying or applying paint to the surface of a free-standing thin film are too high and would break the specimens. In addition, the sizes of individual paint particles are on the order of μms, while the film thickness is only several hundred nanometers, which would be analogous to supporting a large boulder on a thin sheet of paper. == Digital volume correlation == Digital Volume Correlation (DVC, and sometimes called Volumetric-DIC) extends the 2D-DIC algorithms into three dimensions to calculate the full-field 3D deformation from a pair of 3D images. This technique is distinct from 3D-DIC, which only calculates the 3D deformation of an exterior surface using conventional optical images. The DVC algorithm is able to track full-field displacement information in the form of voxels instead of pixels. The theory is similar to above except that another dimension is added: the z-dimension. The displacement is calculated from the correlation of 3D subsets of the reference and deformed volumetric images, which is analogous to the correlation of 2D subsets described above. DVC can be performed using volumetric image datasets. These images can be obtained using confocal microscopy, X-ray computed tomography, Magnetic Resonance Imaging or other techniques. Similar to the other DIC techniques, the images must exhibit a distinct, high-contrast 3D "speckle pattern" to ensure accurate displacement measurement. DVC was first developed in 1999 to study the deformation of trabecular bone using X-ray computed tomography images. Since then, applications of DVC have grown to include granular materials, metals, foams, composites and biological materials. To date it has been used with images acquired by MRI imaging, Computer Tomography (CT), micro-CT, confocal microscopy, and lightsheet microscopy. DVC is currently considered to be ideal in the research world for 3D quantification of local displacements, strains, and stress in biological specimens. It is preferred because of the non-invasiveness of the method over traditional experimental methods. Two of the key challenges are improving the speed and reliability of the DVC measurement. The 3D imaging techniques produce noisier images than conventional 2D optical images, which reduces the quality of the displacement measurement. Computational speed is restricted by the file sizes of 3D images, which are significantly larger than 2D images. For example, an