The Ho–Kashyap algorithm is an iterative method in machine learning for finding a linear decision boundary that separates two linearly separable classes. It was developed by Yu-Chi Ho and Rangasami L. Kashyap in 1965, and usually presented as a problem in linear programming. == Setup == Given a training set consisting of samples from two classes, the Ho–Kashyap algorithm seeks to find a weight vector w {\displaystyle \mathbf {w} } and a margin vector b {\displaystyle \mathbf {b} } such that: Y w = b {\displaystyle \mathbf {Yw} =\mathbf {b} } where Y {\displaystyle \mathbf {Y} } is the augmented data matrix with samples from both classes (with appropriate sign conventions, e.g., samples from class 2 are negated), w {\displaystyle \mathbf {w} } is the weight vector to be determined, and b {\displaystyle \mathbf {b} } is a positive margin vector. The algorithm minimizes the criterion function: J ( w , b ) = | | Y w − b | | 2 {\displaystyle J(\mathbf {w} ,\mathbf {b} )=||\mathbf {Yw} -\mathbf {b} ||^{2}} subject to the constraint that b > 0 {\displaystyle \mathbf {b} >\mathbf {0} } (element-wise). Given a problem of linearly separating two classes, we consider a dataset of elements { ( x i , y i ) } i ∈ 1 : N {\displaystyle \{(\mathbf {x_{i}} ,y_{i})\}_{i\in 1:N}} where y i ∈ { − 1 , + 1 } {\displaystyle y_{i}\in \{-1,+1\}} . Linearly separating them by a perceptron is equivalent to finding weight and bias w , b {\displaystyle \mathbf {w} ,b} for a perceptron, such that: [ y 1 x 1 1 ⋮ ⋮ y N x N 1 ] [ w b ] > 0 {\displaystyle {\begin{bmatrix}y_{1}\mathbf {x} _{1}&1\\\vdots &\vdots \\y_{N}\mathbf {x} _{N}&1\\\end{bmatrix}}{\begin{bmatrix}\mathbf {w} \\b\end{bmatrix}}>0} == Algorithm == The idea of the Ho–Kashyap algorithm is as follows: Given any b {\displaystyle \mathbf {b} } , the corresponding w {\displaystyle \mathbf {w} } is known: It is simply w = Y + b {\displaystyle \mathbf {w} =\mathbf {Y} ^{+}\mathbf {b} } , where Y + {\displaystyle \mathbf {Y} ^{+}} denotes the Moore–Penrose pseudoinverse of Y {\displaystyle \mathbf {Y} } . Therefore, it only remains to find b {\displaystyle \mathbf {b} } by gradient descent. However, the gradient descent may sometimes decrease some of the coordinates of b {\displaystyle \mathbf {b} } , which may cause some coordinates of b {\displaystyle \mathbf {b} } to become negative, which is undesirable. Therefore, whenever some coordinates of b {\displaystyle \mathbf {b} } would have decreased, those coordinates are unchanged instead. As for the coordinates of b {\displaystyle \mathbf {b} } that would increase, those would increase without issue. Formally, the algorithm is as follows: Initialization: Set b ( 0 ) {\displaystyle \mathbf {b} (0)} to an arbitrary positive vector, typically b ( 0 ) = 1 {\displaystyle \mathbf {b} (0)=\mathbf {1} } (a vector of ones). Set the iteration counter k = 0 {\displaystyle k=0} . Set w ( 0 ) = Y + b ( 0 ) {\displaystyle \mathbf {w} (0)=\mathbf {Y} ^{+}\mathbf {b} (0)} Loop until convergence, or until iteration counter exceeds some k m a x {\displaystyle k_{max}} . Error calculation: Compute the error vector: e ( k ) = Y w ( k ) − b ( k ) {\displaystyle \mathbf {e} (k)=\mathbf {Yw} (k)-\mathbf {b} (k)} . Margin update: Update the margin vector: b ( k + 1 ) = b ( k ) + 2 η k ( e ( k ) + | e ( k ) | ) {\displaystyle \mathbf {b} (k+1)=\mathbf {b} (k)+2\eta _{k}(\mathbf {e} (k)+|\mathbf {e} (k)|)} where η k {\displaystyle \eta _{k}} is a positive learning rate parameter, and | e ( k ) | {\displaystyle |\mathbf {e} (k)|} denotes the element-wise absolute value. Weight calculation: Compute the weight vector using the pseudoinverse: w ( k + 1 ) = Y + b ( k + 1 ) {\displaystyle \mathbf {w} (k+1)=\mathbf {Y} ^{+}\mathbf {b} (k+1)} . Convergence check: If | | e ( k ) | | ≤ θ {\displaystyle ||\mathbf {e} (k)||\leq \theta } for some predetermined threshold θ {\displaystyle \theta } (close to zero), then return b ( k + 1 ) , w ( k + 1 ) {\displaystyle \mathbf {b} (k+1),\mathbf {w} (k+1)} . if e ( k ) ≤ 0 {\displaystyle \mathbf {e} (k)\leq \mathbf {0} } (all components non-positive), return "Samples not separable.". Return "Algorithm failed to converge in time.". == Properties == If the training data is linearly separable, the algorithm converges to a solution (where e ( k ) = 0 {\displaystyle \mathbf {e} (k)=\mathbf {0} } ) in a finite number of iterations. If the data is not linearly separable, the algorithm may or may not ever reach the point where e ( k ) = 0 {\displaystyle \mathbf {e} (k)=\mathbf {0} } . However, if it does happen that e ( k ) ≤ 0 {\displaystyle \mathbf {e} (k)\leq \mathbf {0} } at some iteration, this proves non-separability. The convergence rate depends on the choice of the learning rate parameter ρ {\displaystyle \rho } and the degree of linear separability of the data. == Relationship to other algorithms == Perceptron algorithm: Both seek linear separators. The perceptron updates weights incrementally based on individual misclassified samples, while Ho–Kashyap is a batch method that processes all samples to compute the pseudoinverse and updates based on an overall error vector. Linear discriminant analysis (LDA): LDA assumes underlying Gaussian distributions with equal covariances for the classes and derives the decision boundary from these statistical assumptions. Ho–Kashyap makes no explicit distributional assumptions and instead tries to solve a system of linear inequalities directly. Support vector machines (SVM): For linearly separable data, SVMs aim to find the maximum-margin hyperplane. The Ho–Kashyap algorithm finds a separating hyperplane but not necessarily the one with the maximum margin. If the data is not separable, soft-margin SVMs allow for some misclassifications by optimizing a trade-off between margin size and misclassification penalty, while Ho–Kashyap provides a least-squares solution. == Variants == Modified Ho–Kashyap algorithm changes weight calculation step w ( k + 1 ) = Y + b ( k + 1 ) {\displaystyle \mathbf {w} (k+1)=\mathbf {Y} ^{+}\mathbf {b} (k+1)} to w ( k + 1 ) = w ( k ) + η k Y + | e ( k ) | {\displaystyle \mathbf {w} (k+1)=\mathbf {w} (k)+\eta _{k}\mathbf {Y} ^{+}|\mathbf {e} (k)|} . Kernel Ho–Kashyap algorithm: Applies kernel methods (the "kernel trick") to the Ho–Kashyap framework to enable non-linear classification by implicitly mapping data to a higher-dimensional feature space.
3D-Coat
3DCoat is a commercial digital sculpting program from Pilgway designed to create free-form organic and hard surfaced 3D models, with tools which enable users to sculpt, add polygonal topology (automatically or manually), create UV maps (automatically or manually), texture the resulting models with natural painting tools, and render static images or animated "turntable" movies. The program can also be used to modify imported 3D models from a number of commercial 3D software products by means of plugins called Applinks. Imported models can be converted into voxel objects for further refinement and for adding high resolution detail, complete UV unwrapping and mapping, as well as adding PBR textures for displacement, bump maps, specular and diffuse color maps. A live connection to a chosen external 3D application can be established through the Applink pipeline, allowing for the transfer of model and texture information. 3DCoat specializes in voxel sculpting and polygonal sculpting using dynamic patch tessellation technology and polygonal sculpting tools. It includes "auto-retopology", a proprietary skinning algorithm which generates a polygonal mesh skin over any voxel sculpture, composed primarily of quadrangles.
Top 10 AI Voice Assistants Compared (2026)
Comparing the best AI voice assistant? An AI voice assistant 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 voice assistant slots into your workflow and pays for itself fast. Below we compare features, pricing, and real output so you can choose with confidence.
Machine translation of sign languages
The machine translation of sign languages has been possible, albeit in a limited fashion, since 1977. When a research project successfully matched English letters from a keyboard to ASL manual alphabet letters which were simulated on a robotic hand. These technologies translate signed languages into written or spoken language, and written or spoken language to sign language, without the use of a human interpreter. Sign languages possess different phonological features than spoken languages, which has created obstacles for developers. Developers use computer vision and machine learning to recognize specific phonological parameters and epentheses unique to sign languages, and speech recognition and natural language processing allow interactive communication between hearing and deaf people. == Limitations == Sign language translation technologies are limited in the same way as spoken language translation. None can translate with 100% accuracy. In fact, sign language translation technologies are far behind their spoken language counterparts. This is, in no trivial way, due to the fact that signed languages have multiple articulators. Where spoken languages are articulated through the vocal tract, signed languages are articulated through the hands, arms, head, shoulders, torso, and parts of the face. This multi-channel articulation makes translating sign languages very difficult. An additional challenge for sign language MT is the fact that there is no formal written format for signed languages. There are notations systems but no writing system has been adopted widely enough, by the international Deaf community, that it could be considered the 'written form' of a given sign language. Sign Languages then are recorded in various video formats. There is no gold standard parallel corpus that is large enough for SMT, for example. == History == The history of automatic sign language translation started with the development of hardware such as finger-spelling robotic hands. In 1977, a finger-spelling hand project called RALPH (short for "Robotic Alphabet") created a robotic hand that can translate alphabets into finger-spellings. Later, the use of gloves with motion sensors became the mainstream, and some projects such as the CyberGlove and VPL Data Glove were born. The wearable hardware made it possible to capture the signers' hand shapes and movements with the help of the computer software. However, with the development of computer vision, wearable devices were replaced by cameras due to their efficiency and fewer physical restrictions on signers. To process the data collected through the devices, researchers implemented neural networks such as the Stuttgart Neural Network Simulator for pattern recognition in projects such as the CyberGlove. Researchers also use many other approaches for sign recognition. For example, Hidden Markov Models are used to analyze data statistically, and GRASP and other machine learning programs use training sets to improve the accuracy of sign recognition. Fusion of non-wearable technologies such as cameras and Leap Motion controllers have shown to increase the ability of automatic sign language recognition and translation software. == Technologies == === VISICAST === http://www.visicast.cmp.uea.ac.uk/Visicast_index.html === eSIGN project === http://www.visicast.cmp.uea.ac.uk/eSIGN/index.html === The American Sign Language Avatar Project at DePaul University === http://asl.cs.depaul.edu/ === Spanish to LSE === López-Ludeña, Verónica; San-Segundo, Rubén; González, Carlos; López, Juan Carlos; Pardo, José M. (2012), Methodology for developing a Speech into Sign Language Translation System in a New Semantic Domain (PDF), CiteSeerX 10.1.1.1065.5265, S2CID 2724186 === SignAloud === SignAloud is a technology that incorporates a pair of gloves made by a group of students at University of Washington that transliterate American Sign Language (ASL) into English. In February 2015 Thomas Pryor, a hearing student from the University of Washington, created the first prototype for this device at Hack Arizona, a hackathon at the University of Arizona. Pryor continued to develop the invention and in October 2015, Pryor brought Navid Azodi onto the SignAloud project for marketing and help with public relations. Azodi has a rich background and involvement in business administration, while Pryor has a wealth of experience in engineering. In May 2016, the duo told NPR that they are working more closely with people who use ASL so that they can better understand their audience and tailor their product to the needs of these people rather than the assumed needs. However, no further versions have been released since then. The invention was one of seven to win the Lemelson-MIT Student Prize, which seeks to award and applaud young inventors. Their invention fell under the "Use it!" category of the award which includes technological advances to existing products. They were awarded $10,000. The gloves have sensors that track the users hand movements and then send the data to a computer system via Bluetooth. The computer system analyzes the data and matches it to English words, which are then spoken aloud by a digital voice. The gloves do not have capability for written English input to glove movement output or the ability to hear language and then sign it to a deaf person, which means they do not provide reciprocal communication. The device also does not incorporate facial expressions and other nonmanual markers of sign languages, which may alter the actual interpretation from ASL. === ProDeaf === ProDeaf (WebLibras) is a computer software that can translate both text and voice into Portuguese Libras (Portuguese Sign Language) "with the goal of improving communication between the deaf and hearing." There is currently a beta edition in production for American Sign Language as well. The original team began the project in 2010 with a combination of experts including linguists, designers, programmers, and translators, both hearing and deaf. The team originated at Federal University of Pernambuco (UFPE) from a group of students involved in a computer science project. The group had a deaf team member who had difficulty communicating with the rest of the group. In order to complete the project and help the teammate communicate, the group created Proativa Soluções and have been moving forward ever since. The current beta version in American Sign Language is very limited. For example, there is a dictionary section and the only word under the letter 'j' is 'jump'. If the device has not been programmed with the word, then the digital avatar must fingerspell the word. The last update of the app was in June 2016, but ProDeaf has been featured in over 400 stories across the country's most popular media outlets. The application cannot read sign language and turn it into word or text, so it only serves as a one-way communication. Additionally, the user cannot sign to the app and receive an English translation in any form, as English is still in the beta edition. === Kinect Sign Language Translator === Since 2012, researchers from the Chinese Academy of Sciences and specialists of deaf education from Beijing Union University in China have been collaborating with Microsoft Research Asian team to create Kinect Sign Language Translator. The translator consists of two modes: translator mode and communication mode. The translator mode is capable of translating single words from sign into written words and vice versa. The communication mode can translate full sentences and the conversation can be automatically translated with the use of the 3D avatar. The translator mode can also detect the postures and hand shapes of a signer as well as the movement trajectory using the technologies of machine learning, pattern recognition, and computer vision. The device also allows for reciprocal communication because the speech recognition technology allows the spoken language to be translated into the sign language and the 3D modeling avatar can sign back to the deaf people. The original project was started in China based on translating Chinese Sign Language. In 2013, the project was presented at Microsoft Research Faculty Summit and Microsoft company meeting. Currently, this project is also being worked by researchers in the United States to implement American Sign Language translation. As of now, the device is still a prototype, and the accuracy of translation in the communication mode is still not perfect. === SignAll === SignAll is an automatic sign language translation system provided by Dolphio Technologies in Hungary. The team is "pioneering the first automated sign language translation solution, based on computer vision and natural language processing (NLP), to enable everyday communication between individuals with hearing who use spoken English and deaf or hard of hearing individuals who use ASL." The system of SignAll uses Kinect from Microsoft and other web camera
Chris Callison-Burch
Chris Callison-Burch is an American computer scientist and professor of computer and information science at the University of Pennsylvania (Penn), specializing in natural language processing (NLP), artificial intelligence (AI), and crowdsourcing. He is recognised for his contributions to machine translation, paraphrase generation, and the application of large language models (LLMs) to AI challenges, with over 200 publications cited more than 33,000 times. Callison-Burch has influenced public policy on AI and copyright, testifying before the U.S. Congress in 2023 on generative AI’s implications. He serves as the faculty director for Penn’s Online Master of Science in Engineering in AI program. == Education == Callison-Burch earned his PhD in Computer Science from the University of Edinburgh in 2008, focusing on machine translation and paraphrasing techniques. His doctoral research developed statistical methods for generating paraphrases in machine translation systems, laying the foundation for his later NLP work. Prior to his PhD, he studied at Stanford University, where he developed an interest in computational linguistics. == Career == After his PhD, Callison-Burch joined the Centre for Language and Speech Processing at Johns Hopkins University as a research faculty member from 2008 to 2013, working on NLP projects, including machine translation and crowdsourcing for creating training data. In 2013, he joined the University of Pennsylvania as an assistant professor in the Department of Computer and Information Science and was promoted to associate professor in 2017, and to full professor in 2024. At Penn, Callison-Burch teaches courses on AI and NLP, including CIS 5300 (Natural Language Processing) and CIS 5210 (Artificial Intelligence), which attract over 500 students annually. He directs Penn’s Online Master of Science in Engineering in AI program, launched in 2025. He teaches AI and NLP courses on Coursera, reaching thousands of global learners. Callison-Burch was a part-time visiting researcher at Google in 2019 and 2020, where he collaborated on applying Google's LLM to Dungeons & Dragons dialogues. In 2023, he took a sabbatical at the Allen Institute for AI (AI2), where he contributed to vision-language models. == Research == Callison-Burch’s research focuses on NLP, AI, and crowdsourcing, with significant contributions to machine translation, paraphrase generation, and LLMs for tasks like text simplification and bias detection. His early work developed crowdsourcing methods for machine translation, leveraging non-expert annotators for paraphrase-based evaluation, influencing platforms like Amazon Mechanical Turk. Recent projects have included several notable works. Molmo and PixMo (2025) are open-weight vision-language models developed with AI2, achieving state-of-the-art multimodal performance and earning a Best Paper Honourable Mention at CVPR 2025. Also in 2025, his work on Calibrating Large Language Models with Sample Consistency improves LLM reliability via sample-based calibration, presented at NAACL 2025. The Media Bias Detector (2025) is a real-time tool analysing selection and framing bias in news, using LLMs to detect persuasive language differences (e.g., Russian vs. English Wikipedia). Holodeck (2024) is a language-guided system for generating 3D embodied AI environments, presented at CVPR 2024. BORDIRLINES (2024) is a dataset for cross-lingual retrieval-augmented generation, focusing on culturally sensitive tasks. He has co-authored over 200 publications, featured at conferences like ACL, EMNLP, and CVPR. == Awards and recognition == Callison-Burch has received numerous awards: Best Paper Honourable Mention at CVPR 2025 for "Molmo and PixMo". Best Paper Award at the Workshop on Cognitive Modelling and Computational Linguistics (CMCL) 2024 for "Evaluating Vision-Language Models on Bistable Images". Best Paper Award at STARSEM 2016 for "So-Called Non-Subsective Adjectives". Best Paper Award at the Workshop on Sense, Concept and Entity Representations 2017 for "Word Sense Filtering Improves Embedding-Based Lexical Substitution". Honourable Mention Award at CHI 2018 for "A Data-Driven Analysis of Workers’ Earnings on Amazon Mechanical Turk". Google Faculty Research Award (2013) for crowdsourcing in NLP. Sloan Research Fellowship (2014). He has received research funding from Google, Microsoft, Amazon, Facebook, Roblox, DARPA, IARPA, and NSF. His h-index is 72, with over 33,000 citations. He served as General Chair of ACL 2017 and as the Program Co-Chair EMNLP 2015. == Public policy and testimony == On May 17, 2023, Callison-Burch testified before the U.S. House Subcommittee on Courts, Intellectual Property, and the Internet on AI and copyright law. His testimony emphasised generative AI’s role in creative industries and the need for balanced copyright frameworks. He has appeared on Fox News to discuss AI’s societal impact, and discussed its impact with other print news sources. He contributes to AI ethics discussions, including workshops on AI’s effects on writing and creative professions.
Artificial intimacy
Artificial intimacy is a form of human-AI interaction in which an individual will form social connections, emotional bonds, or intimate relationships with various forms of artificial intelligence, including chatbots, virtual assistants, and other artificial entities. Artificially intimate relationships include not only romances, but parasocial relationships with virtual AI characters and the use of griefbots trained on a dead or otherwise lost individual. Artificial intimacy can arise because humans are prone to anthropomorphism. Responses from these AI models are often designed to simulate human interaction. Individuals experiencing artificial intimacy may exhibit attachment, love and commitment to certain AI models, akin to the bonds typically shared between humans. == Causes == === Perceived responsiveness === Robin Dunbar famously proposed that due to emergence of larger groups of humans, vocal communication and language in humans evolved to replace grooming as a means of bonding, arguing that language was a more efficient way to maintain and strengthen social bonds across wider social settings and networks. Further research in this field leads many psychologists to agree that social cognition, affiliative bonding and language in humans are deeply connected. The interpersonal model of intimacy considers communication to be key in affiliative bonding, suggesting that intimacy develops and deepens through open communication between partners in relationship. Specifically, when individuals communicate emotions and perceive their partner as responsive and caring, feelings of closeness and connection are enhanced, building intimacy. Social penetration theory also aligns with the idea of communication being central to intimacy, by explaining how interpersonal relationships develop through gradual increases in self-disclosure. When the benefits of emotional bonding outweigh the costs of vulnerability, individuals will partake in self-disclosure, opening up to one another. Thereby, the literature can be used to provide a proximate explanation for the emergence of artificial intimacy to understand how the phenomenon occurs. Artificial entities are able to mimic interpersonal communication between humans, which in turn can simulate sensations of intimacy within human users though a perceived sense of responsiveness. The relationship between human and AI does not come with the cost of vulnerability or social rejection, which may make self-disclosure easier than with other humans. Altogether, these factors may lead to the experience of anthropomorphism and formation of affiliative relationships. Skjuve et al's interview study on Replika chatbot users further aligns with this explanation, finding that users' perception of chatbots as "accepting, understanding and non-judgmental" facilitated relationship development between the AI and users, and the act of self-disclosure possibly strengthened relationships. Another study on Replika users' reviews and survey results found users perceived chatbots as emotional supportive companions. This evidence further suggests that the perception of artificial entities as capable of empathy and responsiveness in communication facilitate the development of intimate relationships between users and AI. === Loneliness and coping with negative emotions === Research has suggested that humans evolved social bonds as a result of evolutionary pressures that favored cooperation, information exchange and transmission, and group living. Many studies stress the presence of social bonds to be important for human living: research by Baumeister and Leary suggests that humans have a basic psychological need to form and maintain "strong, stable interpersonal relationships", and that a lack of social bonds or sense of belonging leads to negative psychological and physical outcomes. Eisenberger et al's study on the neuroimaging of brain activity suggests that human brains process social rejection and exclusion similarly to physical pain. Furthermore, Song et al's study found that lonely individuals tend to seek more connections in mediated environments, such as online platforms like Facebook. This was suggested to be as a means to reduce their offline loneliness from a lack of in-person interaction, while also fulfilling a need to communicate. Leading on from this, an ultimate explanation for why humans seek the perceived sense of connection from artificial intimacy is to fulfil an evolutionary need for bonding and belonging. Xie et al's study found loneliness to be a driving factor in chatbot interaction. Herbener and Damholdt's study on Danish high school students found that students who sought emotional support or engaged in reciprocal conversations with chatbots were significantly more lonely than their peers, perceived themselves as having less social support, and used the chatbots to cope with negative emotions. The aforementioned notion that chatbots were perceived to have a positive effect on users' negative emotions is also further supported by other studies. Skjuve et al's study found that chatbot relationships may have a positive effect on users' wellbeing. De Freitas et al ran several studies on the effect of chatbots on loneliness, consistently finding evidence suggesting that interaction with chatbots reduces loneliness in users: It was found that existing chatbot users used AI to alleviate loneliness, having an AI companion consistently reduced loneliness over the course of a week, and reductions in loneliness could be explained by chatbot performance—and specifically whether it was able to make users feel heard. Overall the evidence suggests an innate need for bonding evokes feelings of loneliness in users, who turn to artificial intimacy as a low-cost method alleviate these emotions. While many users report positive experiences, some researchers caution that pursuing artificial intimacy may lead to reduced social motivation, social substitution effects, withdrawal from real-life relationships and difficulty discerning reality from fantasy, which may increase longer-term loneliness and isolation. The long-term psychological and societal impacts remain under active investigation.
Büchi automaton
In computer science and automata theory, a deterministic Büchi automaton is a theoretical machine which either accepts or rejects infinite inputs. Such a machine has a set of states and a transition function, which determines which state the machine should move to from its current state when it reads the next input character. Some states are accepting states and one state is the start state. The machine accepts an input if and only if it will pass through an accepting state infinitely many times as it reads the input. A non-deterministic Büchi automaton, later referred to just as a Büchi automaton, has a transition function which may have multiple outputs, leading to many possible paths for the same input; it accepts an infinite input if and only if some possible path is accepting. Deterministic and non-deterministic Büchi automata generalize deterministic finite automata and nondeterministic finite automata to infinite inputs. Each are types of ω-automata. Büchi automata recognize the ω-regular languages, the infinite word version of regular languages. They are named after the Swiss mathematician Julius Richard Büchi, who invented them in 1962. Büchi automata are often used in model checking as an automata-theoretic version of a formula in linear temporal logic. == Formal definition == Formally, a deterministic Büchi automaton is a tuple A = ( Q , Σ , δ , q 0 , F ) {\textstyle A=(Q,\Sigma ,\delta ,q_{0},\mathbf {F} )} that consists of the following components: Q {\textstyle Q} is a finite set. The elements of Q {\textstyle Q} are called the states of A {\textstyle A} . Σ {\textstyle \Sigma } is a finite set called the alphabet of A {\textstyle A} . δ : Q × Σ → Q {\textstyle \delta \colon Q\times \Sigma \to Q} is a function, called the transition function of A {\textstyle A} . q 0 {\textstyle q_{0}} is an element of Q {\textstyle Q} , called the initial state of A {\textstyle A} . F ⊆ Q {\textstyle \mathbf {F} \subseteq Q} is the acceptance condition. A run i _ = i 0 i 1 i 2 ⋯ ∈ Σ ω {\displaystyle {\underline {i}}=i_{0}i_{1}i_{2}\cdots \in \Sigma ^{\omega }} is an infinite string of inputs of A {\displaystyle A} . By calling δ {\displaystyle \delta } recursively, we can extend it to a function δ ω : Σ ω → Q ω {\displaystyle \delta ^{\omega }:\Sigma ^{\omega }\to Q^{\omega }} . A state q ∈ Q {\displaystyle q\in Q} is said to occur infinitely often for a run i _ {\displaystyle {\underline {i}}} when the set { n ∈ N ∣ δ ω ( i _ ) n = q } {\displaystyle \{n\in \mathbb {N} \mid \delta ^{\omega }({\underline {i}})_{n}=q\}} is infinite. Let I n f ( i _ ) {\displaystyle \mathrm {Inf} ({\underline {i}})} be the set of states occurring infinitely often for i _ {\displaystyle {\underline {i}}} . The language of A {\displaystyle A} is then the set of runs of A {\displaystyle A} in which at least one of the infinitely-often occurring states is in F {\textstyle \mathbf {F} } ; in symbols: L ( A ) = { i _ ∈ Σ ω ∣ I n f ( i _ ) ∩ F ≠ ∅ } . {\displaystyle L(A)=\{{\underline {i}}\in \Sigma ^{\omega }\mid \mathrm {Inf} ({\underline {i}})\cap \mathbf {F} \neq \varnothing \}.} In a (non-deterministic) Büchi automaton, the transition function δ {\textstyle \delta } is replaced with a transition relation Δ {\textstyle \Delta } that returns a set of states, and the single initial state q 0 {\textstyle q_{0}} is replaced by a set I {\textstyle I} of initial states. Generally, the term Büchi automaton without qualifier refers to non-deterministic Büchi automata. For more comprehensive formalism see also ω-automaton. == Closure properties == The set of Büchi automata is closed under the following operations. Let A = ( Q A , Σ , Δ A , I A , F A ) {\displaystyle A=(Q_{A},\Sigma ,\Delta _{A},I_{A},{F}_{A})} and B = ( Q B , Σ , Δ B , I B , F B ) {\displaystyle B=(Q_{B},\Sigma ,\Delta _{B},I_{B},{F}_{B})} be Büchi automata and C = ( Q C , Σ , Δ C , I C , F C ) {\displaystyle C=(Q_{C},\Sigma ,\Delta _{C},I_{C},{F}_{C})} be a finite automaton. Union: There is a Büchi automaton that recognizes the language L ( A ) ∪ L ( B ) . {\displaystyle L(A)\cup L(B).} Proof: If we assume, w.l.o.g., Q A ∩ Q B {\displaystyle Q_{A}\cap Q_{B}} is empty then L ( A ) ∪ L ( B ) {\displaystyle L(A)\cup L(B)} is recognized by the Büchi automaton ( Q A ∪ Q B , Σ ∪ Σ , Δ A ∪ Δ B , I A ∪ I B , F A ∪ F B ) . {\displaystyle (Q_{A}\cup Q_{B},\Sigma \cup \Sigma ,\Delta _{A}\cup \Delta _{B},I_{A}\cup I_{B},{F}_{A}\cup {F}_{B}).} Intersection: There is a Büchi automaton that recognizes the language L ( A ) ∩ L ( B ) . {\displaystyle L(A)\cap L(B).} Proof: The Büchi automaton A ′ = ( Q ′ , Σ , Δ ′ , I ′ , F ′ ) {\displaystyle A'=(Q',\Sigma ,\Delta ',I',F')} recognizes L ( A ) ∩ L ( B ) , {\displaystyle L(A)\cap L(B),} where Q ′ = Q A × Q B × { 1 , 2 } {\displaystyle Q'=Q_{A}\times Q_{B}\times \{1,2\}} Δ ′ = Δ 1 ∪ Δ 2 {\displaystyle \Delta '=\Delta _{1}\cup \Delta _{2}} Δ 1 = { ( ( q A , q B , 1 ) , a , ( q A ′ , q B ′ , i ) ) | ( q A , a , q A ′ ) ∈ Δ A and ( q B , a , q B ′ ) ∈ Δ B and if q A ∈ F A then i = 2 else i = 1 } {\displaystyle \Delta _{1}=\{((q_{A},q_{B},1),a,(q'_{A},q'_{B},i))|(q_{A},a,q'_{A})\in \Delta _{A}{\text{ and }}(q_{B},a,q'_{B})\in \Delta _{B}{\text{ and if }}q_{A}\in F_{A}{\text{ then }}i=2{\text{ else }}i=1\}} Δ 2 = { ( ( q A , q B , 2 ) , a , ( q A ′ , q B ′ , i ) ) | ( q A , a , q A ′ ) ∈ Δ A and ( q B , a , q B ′ ) ∈ Δ B and if q B ∈ F B then i = 1 else i = 2 } {\displaystyle \Delta _{2}=\{((q_{A},q_{B},2),a,(q'_{A},q'_{B},i))|(q_{A},a,q'_{A})\in \Delta _{A}{\text{ and }}(q_{B},a,q'_{B})\in \Delta _{B}{\text{ and if }}q_{B}\in F_{B}{\text{ then }}i=1{\text{ else }}i=2\}} I ′ = I A × I B × { 1 } {\displaystyle I'=I_{A}\times I_{B}\times \{1\}} F ′ = { ( q A , q B , 2 ) | q B ∈ F B } {\displaystyle F'=\{(q_{A},q_{B},2)|q_{B}\in F_{B}\}} By construction, r ′ = ( q A 0 , q B 0 , i 0 ) , ( q A 1 , q B 1 , i 1 ) , … {\displaystyle r'=(q_{A}^{0},q_{B}^{0},i^{0}),(q_{A}^{1},q_{B}^{1},i^{1}),\dots } is a run of automaton A' on input word w {\textstyle w} if r A = q A 0 , q A 1 , … {\displaystyle r_{A}=q_{A}^{0},q_{A}^{1},\dots } is run of A {\textstyle A} on w {\textstyle w} and r B = q B 0 , q B 1 , … {\displaystyle r_{B}=q_{B}^{0},q_{B}^{1},\dots } is run of B {\textstyle B} on w {\textstyle w} . r A {\textstyle r_{A}} is accepting and r B {\textstyle r_{B}} is accepting if r ′ {\textstyle r'} is concatenation of an infinite series of finite segments of 1-states (states with third component 1) and 2-states (states with third component 2) alternatively. There is such a series of segments of r ′ {\textstyle r'} if r ′ {\textstyle r'} is accepted by A ′ {\textstyle A'} . Concatenation: There is a Büchi automaton that recognizes the language L ( C ) ⋅ L ( A ) . {\displaystyle L(C)\cdot L(A).} Proof: If we assume, w.l.o.g., Q C ∩ Q A {\displaystyle Q_{C}\cap Q_{A}} is empty then the Büchi automaton A ′ = ( Q C ∪ Q A , Σ , Δ ′ , I ′ , F A ) {\displaystyle A'=(Q_{C}\cup Q_{A},\Sigma ,\Delta ',I',F_{A})} recognizes L ( C ) ⋅ L ( A ) {\displaystyle L(C)\cdot L(A)} , where Δ ′ = Δ A ∪ Δ C ∪ { ( q , a , q ′ ) | q ′ ∈ I A and ∃ f ∈ F C . ( q , a , f ) ∈ Δ C } {\displaystyle \Delta '=\Delta _{A}\cup \Delta _{C}\cup \{(q,a,q')|q'\in I_{A}{\text{ and }}\exists f\in F_{C}.(q,a,f)\in \Delta _{C}\}} if I C ∩ F C is empty then I ′ = I C otherwise I ′ = I C ∪ I A {\displaystyle {\text{ if }}I_{C}\cap F_{C}{\text{ is empty then }}I'=I_{C}{\text{ otherwise }}I'=I_{C}\cup I_{A}} ω-closure: If L ( C ) {\displaystyle L(C)} does not contain the empty word then there is a Büchi automaton that recognizes the language L ( C ) ω . {\displaystyle L(C)^{\omega }.} Proof: The Büchi automaton that recognizes L ( C ) ω {\displaystyle L(C)^{\omega }} is constructed in two stages. First, we construct a finite automaton A ′ {\textstyle A'} such that A ′ {\textstyle A'} also recognizes L ( C ) {\displaystyle L(C)} but there are no incoming transitions to initial states of A ′ {\textstyle A'} . So, A ′ = ( Q C ∪ { q new } , Σ , Δ ′ , { q new } , F C ) , {\displaystyle A'=(Q_{C}\cup \{q_{\text{new}}\},\Sigma ,\Delta ',\{q_{\text{new}}\},F_{C}),} where Δ ′ = Δ C ∪ { ( q new , a , q ′ ) | ∃ q ∈ I C . ( q , a , q ′ ) ∈ Δ C } . {\displaystyle \Delta '=\Delta _{C}\cup \{(q_{\text{new}},a,q')|\exists q\in I_{C}.(q,a,q')\in \Delta _{C}\}.} Note that L ( C ) = L ( A ′ ) {\displaystyle L(C)=L(A')} because L ( C ) {\displaystyle L(C)} does not contain the empty string. Second, we will construct the Büchi automaton A ″ {\textstyle A''} that recognize L ( C ) ω {\displaystyle L(C)^{\omega }} by adding a loop back to the initial state of A ′ {\textstyle A'} . So, A ″ = ( Q C ∪ { q new } , Σ , Δ ″ , { q new } , { q new } ) {\displaystyle A''=(Q_{C}\cup \{q_{\text{new}}\},\Sigma ,\Delta '',\{q_{\text{new}}\},\{q_{\text{new}}\})} , where Δ ″ = Δ ′ ∪ { ( q , a , q new ) | ∃ q ′ ∈ F C . ( q , a , q ′ ) ∈ Δ ′ } . {\displaystyle \Delta ''=\Delta '\cup \{(q,a,q_{\text{new}})|\exists q'\in F_{C}.(q,a,q')\in \Delta '\}.} Complementation: