Accept (automata and complexity theory)

Acceptance is a term from automaton and complexity theory , sub-areas of theoretical computer science . The property that an automaton accepts input is closely related to decidability .

• An algorithm accepts a language A if and only if it returns a positive answer for exactly the elements from A.
• An algorithm decides a language A if and only if it terminates in each case and returns a positive answer for exactly the elements from A (this implies that it returns a negative answer for all inputs that are not in A).

The distinction between accepting and deciding is particularly important if the calculation is nondeterministic (see also NP (complexity class) ) or if there can be infinitely long calculations (see recursive enumeration ).

literature

• Uwe Schöning : Theoretical Computer Science - in a nutshell . Spectrum Academic Publishing House , 2001, ISBN 3-8274-1099-1 .

Web links

Wiktionary: accept  - explanations of meanings, word origins, synonyms, translations