Auxiliary basement machine

from Wikipedia, the free encyclopedia
QS IT
 This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + )

An auxiliary basement machine (eng. Auxiliary pushdown automaton) is a calculation model based on complexity theory .

It was first mentioned by Stephen Cook in 1971 in the Journal of the ACM .

In 1978, Ivan H. Sudborough succeeded in characterizing a complexity-theoretical degree of context-free languages . The model was examined further by Eric Allender, Allan Borodin, Franz-Josef Brandenburg, Clemens Lautemann, Pierre McKenzie, Rolf Niedermeier, Peter Rossmanith , Thomas Schwentick, Martin Tompa and Heribert Vollmer , among others .

properties

If a person wants to sit down and do something bigger, he has to spread all the interim results side by side on the table. At some point the table is full and you start piling up.

The stack corresponds to the pushdown, the storage area of ​​a push-down machine ; the space on the desk is the RAM. Obviously you can accommodate a lot more on the stack than on the RAM. However, you can no longer see the documents in the stack. Only the top one remains visible.

The result of Stephen Cook is: Every language that can be decided in polynomial time can be decided in exponential time by an auxiliary basement machine with logarithmic space constraints and unlimited basement , even deterministically . In addition, the nondeterministic calculation model is not superior to the deterministic one in the case of auxiliary basement machines.

Ivan H. Sudborough restricts the maximum time requirement of the auxiliary basement machines polynomially and characterizes the completion of context-free languages ​​under logarithmic reduction by polynomial-time limited auxiliary basement machines with logarithmic space limit. There are very close relationships here with the complexity classes AC and NC .

swell