Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen. Der Kellerautomat ist ein endlicher Automat, der um einen Kellerspeicher (a.g. Stack) erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.

Die zellulären Automaten bilden einen Aspekt der Kybernetik, der in den Jahren 1943 bis 1953 einen Anfang der Kognitionswissenschaft begründete. Bezeichnung verwendet Zelle und Automat und beabsichtigt damit Assoziationen zu künstlichen Lebewesen. Die Die Erfolge der Von-Neumann-Rechner-Architektur bewirkten für längere Zeit, dass die zellulären Automaten nicht weiterentwickelt wurden. Ab etwa 1970 rückten sie wieder ins Blickfeld und wurden Elemente der künstlichen Intelligenz und der Konnektivität.

Zellularautomaten wurden um 1940 von Stanislaw Ulam in Los Alamos vorgestellt. J. von Neumann, ein damaliger Kollege Ulams, griff die Idee auf und erweiterte sie zu einem universellen Berechnungsmodell. Er stellte einen Zellularautomaten mit 29 Zuständen vor, der ein gegebenes Muster immer wieder selbst reproduzieren konnte. Er beschrieb damit als erster einen Zellularautomaten, der berechnungs- und konstruktionsuniversell ist. Er ist nach Neumann geeignet für Probleme biologischer Organisation, Selbstreproduktion und der Evolution von Komplexität. Damit ist der Zellularautomat auch eine wichtige Grundlage für künstliches Leben.
Bis zu den 1960er Jahren waren die Analogrechner den Digitalrechnern bei einigen Fragestellungen überlegen. Ein analoger Zellulärer Automat zur Simulation von Grundwasserströmungen wird im Artikel Analogrechner genauer beschrieben.
In den 1970er Jahren erlangte John Horton Conways Game of Life Berühmtheit.
1969 veröffentlichte Konrad Zuse sein Buch „Rechnender Raum“, worin er annimmt, dass die Naturgesetze diskreten Regeln folgen und das gesamte Geschehen im Universum das Ergebnis der Arbeit eines gigantischen Zellularautomaten sei.
1983 veröffentlichte Stephen Wolfram eine Reihe von grundlegenden Arbeiten zu Zellularautomaten und 2002 das Buch A New Kind of Science.