Similarity learning is an area of supervised machine learning in artificial intelligence. It is closely related to regression and classification, but the goal is to learn a similarity function that measures how similar or related two objects are. It has applications in ranking, in recommendation systems, visual identity tracking, face verification, and speaker verification. == Learning setup == There are four common setups for similarity and metric distance learning. Regression similarity learning In this setup, pairs of objects are given ( x i 1 , x i 2 ) {\displaystyle (x_{i}^{1},x_{i}^{2})} together with a measure of their similarity y i ∈ R {\displaystyle y_{i}\in R} . The goal is to learn a function that approximates f ( x i 1 , x i 2 ) ∼ y i {\displaystyle f(x_{i}^{1},x_{i}^{2})\sim y_{i}} for every new labeled triplet example ( x i 1 , x i 2 , y i ) {\displaystyle (x_{i}^{1},x_{i}^{2},y_{i})} . This is typically achieved by minimizing a regularized loss min W ∑ i l o s s ( w ; x i 1 , x i 2 , y i ) + r e g ( w ) {\displaystyle \min _{W}\sum _{i}loss(w;x_{i}^{1},x_{i}^{2},y_{i})+reg(w)} . Classification similarity learning Given are pairs of similar objects ( x i , x i + ) {\displaystyle (x_{i},x_{i}^{+})} and non similar objects ( x i , x i − ) {\displaystyle (x_{i},x_{i}^{-})} . An equivalent formulation is that every pair ( x i 1 , x i 2 ) {\displaystyle (x_{i}^{1},x_{i}^{2})} is given together with a binary label y i ∈ { 0 , 1 } {\displaystyle y_{i}\in \{0,1\}} that determines if the two objects are similar or not. The goal is again to learn a classifier that can decide if a new pair of objects is similar or not. Ranking similarity learning Given are triplets of objects ( x i , x i + , x i − ) {\displaystyle (x_{i},x_{i}^{+},x_{i}^{-})} whose relative similarity obey a predefined order: x i {\displaystyle x_{i}} is known to be more similar to x i + {\displaystyle x_{i}^{+}} than to x i − {\displaystyle x_{i}^{-}} . The goal is to learn a function f {\displaystyle f} such that for any new triplet of objects ( x , x + , x − ) {\displaystyle (x,x^{+},x^{-})} , it obeys f ( x , x + ) > f ( x , x − ) {\displaystyle f(x,x^{+})>f(x,x^{-})} (contrastive learning). This setup assumes a weaker form of supervision than in regression, because instead of providing an exact measure of similarity, one only has to provide the relative order of similarity. For this reason, ranking-based similarity learning is easier to apply in real large-scale applications. Locality sensitive hashing (LSH) Hashes input items so that similar items map to the same "buckets" in memory with high probability (the number of buckets being much smaller than the universe of possible input items). It is often applied in nearest neighbor search on large-scale high-dimensional data, e.g., image databases, document collections, time-series databases, and genome databases. A common approach for learning similarity is to model the similarity function as a bilinear form. For example, in the case of ranking similarity learning, one aims to learn a matrix W that parametrizes the similarity function f W ( x , z ) = x T W z {\displaystyle f_{W}(x,z)=x^{T}Wz} . When data is abundant, a common approach is to learn a siamese network – a deep network model with parameter sharing. == Metric learning == Similarity learning is closely related to distance metric learning. Metric learning is the task of learning a distance function over objects. A metric or distance function has to obey four axioms: non-negativity, identity of indiscernibles, symmetry and subadditivity (or the triangle inequality). In practice, metric learning algorithms ignore the condition of identity of indiscernibles and learn a pseudo-metric. When the objects x i {\displaystyle x_{i}} are vectors in R d {\displaystyle R^{d}} , then any matrix W {\displaystyle W} in the symmetric positive semi-definite cone S + d {\displaystyle S_{+}^{d}} defines a distance pseudo-metric of the space of x through the form D W ( x 1 , x 2 ) 2 = ( x 1 − x 2 ) ⊤ W ( x 1 − x 2 ) {\displaystyle D_{W}(x_{1},x_{2})^{2}=(x_{1}-x_{2})^{\top }W(x_{1}-x_{2})} . When W {\displaystyle W} is a symmetric positive definite matrix, D W {\displaystyle D_{W}} is a metric. Moreover, as any symmetric positive semi-definite matrix W ∈ S + d {\displaystyle W\in S_{+}^{d}} can be decomposed as W = L ⊤ L {\displaystyle W=L^{\top }L} where L ∈ R e × d {\displaystyle L\in R^{e\times d}} and e ≥ r a n k ( W ) {\displaystyle e\geq rank(W)} , the distance function D W {\displaystyle D_{W}} can be rewritten equivalently D W ( x 1 , x 2 ) 2 = ( x 1 − x 2 ) ⊤ L ⊤ L ( x 1 − x 2 ) = ‖ L ( x 1 − x 2 ) ‖ 2 2 {\displaystyle D_{W}(x_{1},x_{2})^{2}=(x_{1}-x_{2})^{\top }L^{\top }L(x_{1}-x_{2})=\|L(x_{1}-x_{2})\|_{2}^{2}} . The distance D W ( x 1 , x 2 ) 2 = ‖ x 1 ′ − x 2 ′ ‖ 2 2 {\displaystyle D_{W}(x_{1},x_{2})^{2}=\|x_{1}'-x_{2}'\|_{2}^{2}} corresponds to the Euclidean distance between the transformed feature vectors x 1 ′ = L x 1 {\displaystyle x_{1}'=Lx_{1}} and x 2 ′ = L x 2 {\displaystyle x_{2}'=Lx_{2}} . Many formulations for metric learning have been proposed. Some well-known approaches for metric learning include learning from relative comparisons, which is based on the triplet loss, large margin nearest neighbor, and information theoretic metric learning (ITML). In statistics, the covariance matrix of the data is sometimes used to define a distance metric called Mahalanobis distance. == Applications == Similarity learning is used in information retrieval for learning to rank, in face verification or face identification, and in recommendation systems. Also, many machine learning approaches rely on some metric. This includes unsupervised learning such as clustering, which groups together close or similar objects. It also includes supervised approaches like K-nearest neighbor algorithm which rely on labels of nearby objects to decide on the label of a new object. Metric learning has been proposed as a preprocessing step for many of these approaches. == Scalability == Metric and similarity learning scale quadratically with the dimension of the input space, as can easily see when the learned metric has a bilinear form f W ( x , z ) = x T W z {\displaystyle f_{W}(x,z)=x^{T}Wz} . Scaling to higher dimensions can be achieved by enforcing a sparseness structure over the matrix model, as done with HDSL, and with COMET. == Software == metric-learn is a free software Python library which offers efficient implementations of several supervised and weakly-supervised similarity and metric learning algorithms. The API of metric-learn is compatible with scikit-learn. OpenMetricLearning is a Python framework to train and validate the models producing high-quality embeddings. == Further information == For further information on this topic, see the surveys on metric and similarity learning by Bellet et al. and Kulis.
Intel Threat Detection Technology
Intel Threat Detection Technology (TDT) is a CPU-level technology created by Intel in 2018 to enable host endpoint protections to use a CPU's low-level access to detect threats to a system. TDT consists of multiple components including Accelerated Memory Scanning, which uses the CPU's integrated GPU to scan memory, and Advanced Platform Telemetry, which uses processor-level activity monitoring to detect unusual activity. It is supported on sixth-generation or newer Intel Core CPUs and additional capabilities were added to the 11th generation Core processors. Intel TDT is integrated into several third-party anti-malware solutions including Microsoft Defender, Check Point Harmony Endpoint, CrowdStrike Falcon, and others. == Accelerated Memory Scanning == Accelerated Memory Scanning (also referred to as "Advanced Memory Scanning") uses the CPU's integrated GPU to scan memory for malicious code, instead of using the CPU directly. This improves system responsiveness during anti-malware scanning. and lowers power consumption. Features include pattern matching, using random forest decision trees, string extraction, entropy calculation, and Euclidean clustering. == Advanced Platform Telemetry == Advanced Platform Telemetry collects CPU-level telemetry to detect uncommon activity patterns which might be indicative of malware. The telemetry data is collected from the CPU performance monitoring unit (PMU) and doesn't require a large signature database to detect malware. Instead, it uses machine-learning based correlations to identify indicators of attack For example, Microsoft Defender is able to use TDT's Advanced Platform Telemetry features to detect processor usage patterns indicative of ransomware and cryptojacking with TDT so it can detect them.
MRF optimization via dual decomposition
In dual decomposition a problem is broken into smaller subproblems and a solution to the relaxed problem is found. This method can be employed for MRF optimization. Dual decomposition is applied to markov logic programs as an inference technique. == Background == Discrete MRF Optimization (inference) is very important in Machine Learning and Computer vision, which is realized on CUDA graphical processing units. Consider a graph G = ( V , E ) {\displaystyle G=(V,E)} with nodes V {\displaystyle V} and Edges E {\displaystyle E} . The goal is to assign a label l p {\displaystyle l_{p}} to each p ∈ V {\displaystyle p\in V} so that the MRF Energy is minimized: (1) min Σ p ∈ V θ p ( l p ) + Σ p q ∈ ε θ p q ( l p ) ( l q ) {\displaystyle \min \Sigma _{p\in V}\theta _{p}(l_{p})+\Sigma _{pq\in \varepsilon }\theta _{pq}(l_{p})(l_{q})} Major MRF Optimization methods are based on Graph cuts or Message passing. They rely on the following integer linear programming formulation (2) min x E ( θ , x ) = θ . x = ∑ p ∈ V θ p . x p + ∑ p q ∈ ε θ p q . x p q {\displaystyle \min _{x}E(\theta ,x)=\theta .x=\sum _{p\in V}\theta _{p}.x_{p}+\sum _{pq\in \varepsilon }\theta _{pq}.x_{pq}} In many applications, the MRF-variables are {0,1}-variables that satisfy: x p ( l ) = 1 {\displaystyle x_{p}(l)=1} ⇔ {\displaystyle \Leftrightarrow } label l {\displaystyle l} is assigned to p {\displaystyle p} , while x p q ( l , l ′ ) = 1 {\displaystyle x_{pq}(l,l^{\prime })=1} , labels l , l ′ {\displaystyle l,l^{\prime }} are assigned to p , q {\displaystyle p,q} . == Dual Decomposition == The main idea behind decomposition is surprisingly simple: decompose your original complex problem into smaller solvable subproblems, extract a solution by cleverly combining the solutions from these subproblems. A sample problem to decompose: min x Σ i f i ( x ) {\displaystyle \min _{x}\Sigma _{i}f^{i}(x)} where x ∈ C {\displaystyle x\in C} In this problem, separately minimizing every single f i ( x ) {\displaystyle f^{i}(x)} over x {\displaystyle x} is easy; but minimizing their sum is a complex problem. So the problem needs to get decomposed using auxiliary variables { x i } {\displaystyle \{x^{i}\}} and the problem will be as follows: min { x i } , x Σ i f i ( x i ) {\displaystyle \min _{\{x^{i}\},x}\Sigma _{i}f^{i}(x^{i})} where x i ∈ C , x i = x {\displaystyle x^{i}\in C,x^{i}=x} Now we can relax the constraints by multipliers { λ i } {\displaystyle \{\lambda ^{i}\}} which gives us the following Lagrangian dual function: g ( { λ i } ) = min { x i ∈ C } , x Σ i f i ( x i ) + Σ i λ i . ( x i − x ) = min { x i ∈ C } , x Σ i [ f i ( x i ) + λ i . x i ] − ( Σ i λ i ) x {\displaystyle g(\{\lambda ^{i}\})=\min _{\{x^{i}\in C\},x}\Sigma _{i}f^{i}(x^{i})+\Sigma _{i}\lambda ^{i}.(x^{i}-x)=\min _{\{x^{i}\in C\},x}\Sigma _{i}[f^{i}(x^{i})+\lambda ^{i}.x^{i}]-(\Sigma _{i}\lambda ^{i})x} Now we eliminate x {\displaystyle x} from the dual function by minimizing over x {\displaystyle x} and dual function becomes: g ( { λ i } ) = min { x i ∈ C } Σ i [ f i ( x i ) + λ i . x i ] {\displaystyle g(\{\lambda ^{i}\})=\min _{\{x^{i}\in C\}}\Sigma _{i}[f^{i}(x^{i})+\lambda ^{i}.x^{i}]} We can set up a Lagrangian dual problem: (3) max { λ i } ∈ Λ g ( λ i ) = Σ i g i ( x i ) , {\displaystyle \max _{\{\lambda ^{i}\}\in \Lambda }g({\lambda ^{i}})=\Sigma _{i}g^{i}(x^{i}),} The Master problem (4) g i ( x i ) = m i n x i f i ( x i ) + λ i . x i {\displaystyle g^{i}(x^{i})=min_{x^{i}}f^{i}(x^{i})+\lambda ^{i}.x^{i}} where x i ∈ C {\displaystyle x^{i}\in C} The Slave problems == MRF optimization via Dual Decomposition == The original MRF optimization problem is NP-hard and we need to transform it into something easier. τ {\displaystyle \tau } is a set of sub-trees of graph G {\displaystyle G} where its trees cover all nodes and edges of the main graph. And MRFs defined for every tree T {\displaystyle T} in τ {\displaystyle \tau } will be smaller. The vector of MRF parameters is θ T {\displaystyle \theta ^{T}} and the vector of MRF variables is x T {\displaystyle x^{T}} , these two are just smaller in comparison with original MRF vectors θ , x {\displaystyle \theta ,x} . For all vectors θ T {\displaystyle \theta ^{T}} we'll have the following: (5) ∑ T ∈ τ ( p ) θ p T = θ p , ∑ T ∈ τ ( p q ) θ p q T = θ p q . {\displaystyle \sum _{T\in \tau (p)}\theta _{p}^{T}=\theta _{p},\sum _{T\in \tau (pq)}\theta _{pq}^{T}=\theta _{pq}.} Where τ ( p ) {\displaystyle \tau (p)} and τ ( p q ) {\displaystyle \tau (pq)} denote all trees of τ {\displaystyle \tau } than contain node p {\displaystyle p} and edge p q {\displaystyle pq} respectively. We simply can write: (6) E ( θ , x ) = ∑ T ∈ τ E ( θ T , x T ) {\displaystyle E(\theta ,x)=\sum _{T\in \tau }E(\theta ^{T},x^{T})} And our constraints will be: (7) x T ∈ χ T , x T = x | T , ∀ T ∈ τ {\displaystyle x^{T}\in \chi ^{T},x^{T}=x_{|T},\forall T\in \tau } Our original MRF problem will become: (8) min { x T } , x Σ T ∈ τ E ( θ T , x T ) {\displaystyle \min _{\{x^{T}\},x}\Sigma _{T\in \tau }E(\theta ^{T},x^{T})} where x T ∈ χ T , ∀ T ∈ τ {\displaystyle x^{T}\in \chi ^{T},\forall T\in \tau } and x T ∈ x | T , ∀ T ∈ τ {\displaystyle x^{T}\in x_{|T},\forall T\in \tau } And we'll have the dual problem we were seeking: (9) max { λ T } ∈ Λ g ( { λ T } ) = ∑ T ∈ τ g T ( λ T ) , {\displaystyle \max _{\{\lambda ^{T}\}\in \Lambda }g(\{\lambda ^{T}\})=\sum _{T\in \tau }g^{T}(\lambda ^{T}),} The Master problem where each function g T ( . ) {\displaystyle g^{T}(.)} is defined as: (10) g T ( λ T ) = min x T E ( θ T + λ T , x T ) {\displaystyle g^{T}(\lambda ^{T})=\min _{x^{T}}E(\theta ^{T}+\lambda ^{T},x^{T})} where x T ∈ χ T {\displaystyle x^{T}\in \chi ^{T}} The Slave problems == Theoretical Properties == Theorem 1. Lagrangian relaxation (9) is equivalent to the LP relaxation of (2). min { x T } , x { E ( x , θ ) | x p T = s p , x T ∈ CONVEXHULL ( χ T ) } {\displaystyle \min _{\{x^{T}\},x}\{E(x,\theta )|x_{p}^{T}=s_{p},x^{T}\in {\text{CONVEXHULL}}(\chi ^{T})\}} Theorem 2. If the sequence of multipliers { α t } {\displaystyle \{\alpha _{t}\}} satisfies α t ≥ 0 , lim t → ∞ α t = 0 , ∑ t = 0 ∞ α t = ∞ {\displaystyle \alpha _{t}\geq 0,\lim _{t\to \infty }\alpha _{t}=0,\sum _{t=0}^{\infty }\alpha _{t}=\infty } then the algorithm converges to the optimal solution of (9). Theorem 3. The distance of the current solution { θ T } {\displaystyle \{\theta ^{T}\}} to the optimal solution { θ ¯ T } {\displaystyle \{{\bar {\theta }}^{T}\}} , which decreases at every iteration. Theorem 4. Any solution obtained by the method satisfies the WTA (weak tree agreement) condition. Theorem 5. For binary MRFs with sub-modular energies, the method computes a globally optimal solution.
Vector quantization
Vector quantization (VQ) is a classical quantization technique from signal processing that allows the modeling of probability density functions by the distribution of prototype vectors. Developed in the early 1980s by Robert M. Gray, it was originally used for data compression. It works by dividing a large set of points (vectors) into groups having approximately the same number of points closest to them. Each group is represented by its centroid point, as in k-means and some other clustering algorithms. In simpler terms, vector quantization chooses a set of points to represent a larger set of points. The density matching property of vector quantization is powerful, especially for identifying the density of large and high-dimensional data. Since data points are represented by the index of their closest centroid, commonly occurring data have low error, and rare data high error. This is why VQ is suitable for lossy data compression. It can also be used for lossy data correction and density estimation. Vector quantization is based on the competitive learning paradigm, so it is closely related to the self-organizing map model and to sparse coding models used in deep learning algorithms such as autoencoder. == Training == One simple training algorithm for vector quantization is: Pick a sample point at random Move the nearest quantization vector centroid towards this sample point, by a small fraction of the distance Repeat A more sophisticated algorithm reduces the bias in the density matching estimation and ensures that all points are used, by including an extra sensitivity parameter: Increase each centroid's sensitivity s i {\displaystyle s_{i}} by a small amount Pick a sample point P {\displaystyle P} at random For each quantization vector centroid c i {\displaystyle c_{i}} , let d ( P , c i ) {\displaystyle d(P,c_{i})} denote the distance of P {\displaystyle P} and c i {\displaystyle c_{i}} Find the centroid c i {\displaystyle c_{i}} for which d ( P , c i ) − s i {\displaystyle d(P,c_{i})-s_{i}} is the smallest Move c i {\displaystyle c_{i}} towards P {\displaystyle P} by a small fraction of the distance Set s i {\displaystyle s_{i}} to zero Repeat It is desirable to use a cooling schedule to produce convergence: see Simulated annealing. Another simple method is LBG, which is based on k-means. The algorithm can be iteratively updated with "live" data, rather than by picking random points from a data set, but this will introduce some bias if the data are temporally correlated over many samples. == Applications == Vector quantization is used for lossy data compression, lossy data correction, pattern recognition, density estimation and clustering. Lossy data correction, or prediction, is used to recover data missing from some dimensions. It is done by finding the nearest group with the data dimensions available, then predicting the result based on the values for the missing dimensions, assuming that they will have the same value as the group's centroid. For density estimation, the area/volume that is closer to a particular centroid than to any other is inversely proportional to the density (due to the density matching property of the algorithm). === Use in data compression === Vector quantization, also called "block quantization" or "pattern matching quantization" is often used in lossy data compression. It works by encoding values from a multidimensional vector space into a finite set of values from a discrete subspace of lower dimension. A lower-space vector requires less storage space, so the data is compressed. Due to the density matching property of vector quantization, the compressed data has errors that are inversely proportional to density. The transformation is usually done by projection or by using a codebook. In some cases, a codebook can be also used to entropy code the discrete value in the same step, by generating a prefix coded variable-length encoded value as its output. The set of discrete amplitude levels is quantized jointly rather than each sample being quantized separately. Consider a k-dimensional vector [ x 1 , x 2 , . . . , x k ] {\displaystyle [x_{1},x_{2},...,x_{k}]} of amplitude levels. It is compressed by choosing the nearest matching vector from a set of n-dimensional vectors [ y 1 , y 2 , . . . , y n ] {\displaystyle [y_{1},y_{2},...,y_{n}]} , with n < k. All possible combinations of the n-dimensional vector [ y 1 , y 2 , . . . , y n ] {\displaystyle [y_{1},y_{2},...,y_{n}]} form the vector space to which all the quantized vectors belong. Only the index of the codeword in the codebook is sent instead of the quantized values. This conserves space and achieves more compression. Twin vector quantization (VQF) is part of the MPEG-4 standard dealing with time domain weighted interleaved vector quantization. === Video codecs based on vector quantization === Bink video Cinepak Daala is transform-based but uses pyramid vector quantization on transformed coefficients Digital Video Interactive: Production-Level Video and Real-Time Video Indeo Microsoft Video 1 QuickTime: Apple Video (RPZA) and Graphics Codec (SMC) Sorenson SVQ1 and SVQ3 Smacker video VQA format, used in many games The usage of video codecs based on vector quantization has declined significantly in favor of those based on motion compensated prediction combined with transform coding, e.g. those defined in MPEG standards, as the low decoding complexity of vector quantization has become less relevant. === Audio codecs based on vector quantization === AMR-WB+ CELP CELT (now part of Opus) is transform-based but uses pyramid vector quantization on transformed coefficients Codec 2 DTS G.729 iLBC Ogg Vorbis TwinVQ === Use in pattern recognition === VQ was also used in the eighties for speech and speaker recognition. Recently it has also been used for efficient nearest neighbor search and on-line signature recognition. In pattern recognition applications, one codebook is constructed for each class (each class being a user in biometric applications) using acoustic vectors of this user. In the testing phase the quantization distortion of a testing signal is worked out with the whole set of codebooks obtained in the training phase. The codebook that provides the smallest vector quantization distortion indicates the identified user. The main advantage of VQ in pattern recognition is its low computational burden when compared with other techniques such as dynamic time warping (DTW) and hidden Markov model (HMM). The main drawback when compared to DTW and HMM is that it does not take into account the temporal evolution of the signals (speech, signature, etc.) because all the vectors are mixed up. In order to overcome this problem a multi-section codebook approach has been proposed. The multi-section approach consists of modelling the signal with several sections (for instance, one codebook for the initial part, another one for the center and a last codebook for the ending part). === Use as clustering algorithm === As VQ is seeking for centroids as density points of nearby lying samples, it can be also directly used as a prototype-based clustering method: each centroid is then associated with one prototype. By aiming to minimize the expected squared quantization error and introducing a decreasing learning gain fulfilling the Robbins-Monro conditions, multiple iterations over the whole data set with a concrete but fixed number of prototypes converges to the solution of k-means clustering algorithm in an incremental manner. === Generative adversarial networks (GAN) === VQ has been used to quantize a feature representation layer in the discriminator of generative adversarial networks. The feature quantization (FQ) technique performs implicit feature matching. It improves the GAN training, and yields an improved performance on a variety of popular GAN models: BigGAN for image generation, StyleGAN for face synthesis, and U-GAT-IT for unsupervised image-to-image translation.
Top 10 AI Text-to-image Tools Compared (2026)
Comparing the best AI text-to-image tool? An AI text-to-image tool is software that uses machine learning to help you get more done — it lowers the barrier so anyone can produce professional output. Privacy matters too: check whether your data trains the model and whether a no-log or enterprise tier is available. Whether you are a beginner or a pro, the right AI text-to-image tool slots into your workflow and pays for itself fast. Below we compare features, pricing, and real output so you can choose with confidence.
LemonStand
LemonStand was a Canadian e-commerce company headquartered in Vancouver, British Columbia, that developed cloud-based computer software for online retailers. LemonStand was shut down on June 5, 2019. == History == LemonStand Version 1 was launched on July 28, 2001. It is written in the PHP programming language. Version 1 was released as an on-premises proprietary licensed software, and the commercial license was not free. However, there was a free trial license available. June 2012, LemonStand raised seed funding from the BDC Venture Capital, and a group of angel investors. December 20, 2013, a cloud-based SaaS version of the LemonStand eCommerce platform was released publicly. May 9, 2014, LemonStand and Payfirma, a payments processing company, partnered to provide integrated services for online retailers. May 3, 2016, LemonStand raised funding from BDC Venture Capital and Silicon Valley–based angel investors. March 5, 2019, LemonStand announced their intention to shut down on June 5, 2019. LemonStand was quietly acquired by Mailchimp at the end of February. == Pricing == LemonStand offered three levels of service plans. LemonStand did not charge any transaction fees.
Muller automaton
In automata theory, a Muller automaton is a type of an ω-automaton. The acceptance condition separates a Muller automaton from other ω-automata. The Muller automaton is defined using a Muller acceptance condition, i.e. the set of all states visited infinitely often must be an element of the acceptance set. Both deterministic and non-deterministic Muller automata recognize the ω-regular languages. They are named after David E. Muller, an American mathematician and computer scientist, who invented them in 1963. == Formal definition == Formally, a deterministic Muller-automaton is a tuple A = (Q,Σ,δ,q0,F) that consists of the following information: Q is a finite set. The elements of Q are called the states of A. Σ is a finite set called the alphabet of A. δ: Q × Σ → Q is a function, called the transition function of A. q0 is an element of Q, called the initial state. F is a set of sets of states. Formally, F ⊆ P(Q) where P(Q) is powerset of Q. F defines the acceptance condition. A accepts exactly those runs in which the set of infinitely often occurring states is an element of F In a non-deterministic Muller automaton, the transition function δ is replaced with a transition relation Δ that returns a set of states and the initial state q0 is replaced by a set of initial states Q0. Generally, 'Muller automaton' refers to a non-deterministic Muller automaton. For more comprehensive formalisation look at ω-automaton. == Equivalence with other ω-automata == The Muller automata are equally expressive as parity automata, Rabin automata, Streett automata, and non-deterministic Büchi automata, to mention some, and strictly more expressive than the deterministic Büchi automata. The equivalence of the above automata and non-deterministic Muller automata can be shown very easily as the accepting conditions of these automata can be emulated using the acceptance condition of Muller automata and vice versa. McNaughton's theorem demonstrates the equivalence of non-deterministic Büchi automaton and deterministic Muller automaton. Thus, deterministic and non-deterministic Muller automata are equivalent in terms of the languages they can accept. == Transformation to non-deterministic Muller automata == Following is a list of automata constructions that each transforms a type of ω-automata to a non-deterministic Muller automaton. From Büchi automata If B is the set of final states in a Büchi automaton with the set of states Q, we can construct a Muller automaton with same set of states, transition function and initial state with the Muller accepting condition as F = { X | X ∈ P(Q) ∧ X ∩ B ≠ ∅}. From Rabin automata/parity automata Similarly, the Rabin conditions ( E j , F j ) {\displaystyle (E_{j},F_{j})} can be emulated by constructing the acceptance set in the Muller automaton as all sets F ⊆ Q {\displaystyle F\subseteq Q} that satisfy F ∩ E j = ∅ {\displaystyle F\cap E_{j}=\emptyset } and F ∩ F j ≠ ∅ {\displaystyle F\cap F_{j}\neq \emptyset } , for some j. Note that this covers the case of parity automata too, as the parity acceptance condition can be expressed as a Rabin acceptance condition easily. From Streett automata The Streett conditions ( E j , F j ) {\displaystyle (E_{j},F_{j})} can be emulated by constructing the acceptance set in the Muller automaton as all sets F ⊆ Q {\displaystyle F\subseteq Q} that satisfy F ∩ F j = ∅ ⟹ F ∩ E j = ∅ {\displaystyle F\cap F_{j}=\emptyset \implies F\cap E_{j}=\emptyset } , for all j. == Transformation to deterministic Muller automata == From Büchi automaton McNaughton's theorem provides a procedure to transform any non-deterministic Büchi automaton into a deterministic Muller automaton.