NBA

In computer science, NBA stands for „Non-deterministic Bűchi Automaton.“ It is a type of computational model used in formal verification and automata theory. An NBA is a finite state machine that operates under non-deterministic conditions, meaning that for some states and inputs, there may be multiple possible transitions to different states.

The primary purpose of an NBA is to accept infinite sequences of input symbols, where the acceptance condition is based on the occurrence of certain states infinitely often. Specifically, an NBA accepts an infinite input if there exists at least one path through the automaton where some designated states (often called „accept states“) are visited infinitely many times.

Non-deterministic Bűchi automata are particularly useful in verifying properties of systems that exhibit infinite behavior, such as concurrent systems or reactive systems, and they are often used in model checking, a method for verifying the correctness of hardware and software systems against specified properties.

The relationship between NBA and other automata, such as deterministic Bűchi automata (DBA), is important in understanding the complexity and capabilities of various computational models.