Neural network pushdown automaton
Architectures AIMech:NeuralNetworkPushdownAutomaton DRAFT
Aliases: NNPDA
A recurrent state-controller architecture whose signed action output pushes or removes fractional quantities of input symbols on an external stack and whose read neurons return the symbol content within a fixed depth at the stack top.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 577 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 4, 0, 0 lines. All distinct match contents were read and concern discovery leads and reviewed context, not an existing exact record. Semantic matching inspected 63 AIO and 146 native definitions, with unchanged preceding rows verified and new matches read. Four full annotated AIO node/edge/generated contexts and four full native records were inspected. NNPDA stores input-symbol quantities and uses one signed action and a top-unit-depth symbol read, unlike the 2015 Stack RNN learned-value/softmax-mixture updates. List RNN uses movable-head insertion and bidirectional movement; GF-RNN pair gates and Clockwork module schedules define different recurrent mechanisms. The source first/second/third-order controllers and hinted settings remain configurations of one inspected NNPDA family. RecurrentNeuralNetwork is the selected broader architecture mapping; none of the three other full AIO contexts establishes exact identity or a better broader target.
Claims & Grounded Evidence
6 Claims
Mechanism
#fractional-symbol-stack
The inspected formulation stores ordered symbol labels with continuous quantities. A positive action pushes the current input symbol with that quantity, a negative action removes its magnitude across successive top entries, and a small action performs no operation. The reported simulations use action thresholds above 0.1 for push, below -0.1 for pop and strictly between them for no-op. Read neurons aggregate symbol quantities in the top unit of stack depth. This is a signed-operation fractional stack, not a softmax-weighted average of separate push and pop state transitions. Exact threshold endpoints and empty-stack or underflow behavior are not specified by this manuscript.
Mechanism
#controller-and-network-order
State neurons receive recurrent state, input-symbol and stack-read information; a separate nonrecurrent action neuron controls the stack. The manuscript describes first-order concatenated input/state/read terms, second-order state-by-input/read interactions and third-order state-by-input-by-read interactions. These are controller parameterization choices within NNPDA, not three different memory data structures. An end marker supports final classification; state transitions and stack manipulation are learned together.
Scope
#joint-loss-and-rejection-boundary
For legal strings the displayed terminal loss is one half of (1-S_out)^2+L^2, combining an accepting output with empty stack length. For illegal strings Equation 2 is max(S_out-L,0). Its zero-loss condition is L>=S_out; by itself this does not force S_out=0 or L>1, despite the more categorical accompanying prose. For example, positive fractional S_out and a larger fractional L give zero illegal loss. The objective alone therefore does not certify a discrete rejecting state or exact learned recognizer.
Limitation
#approximate-sensitivities-and-implementation-scope
Training propagates recurrent weight sensitivities and updates weights after a complete string, extending real-time recurrent learning to stack feedback. The authors explicitly replace the history-dependent stack-read derivative with a first-order approximation, justified heuristically when actions are large and training is sufficiently advanced. The displayed stack-length increment also does not specify all threshold and underflow cases. Continuous quantities do not establish a globally smooth, exact gradient implementation. The manuscript describes signed actions separately from its logistic state equations; no unreported signed-output transform or executable boundary policy is inferred.
Scope
#dead-state-hints
The optional hint protocol assumes a teacher or oracle that identifies prefixes which can no longer extend to a legal string. It stops processing those examples, trains a designated dead-state neuron and drops the stack-length penalty for them. An illegal string that could still extend to a legal one does not receive that treatment. Such hints supply extra grammar information beyond whole-string labels, so the hinted comparisons are not evidence for the same supervision setting as the unhinted runs.
Limitation
#extraction-and-evaluation-limits
The source trains incrementally from shorter to longer strings on selected small deterministic context-free languages, comparing controller orders and hinted versus unhinted settings. Tables include runs that did not converge, and the conclusion says third order is not invariably better or faster. Quantizing learned states and actions is a separate extraction step; it is not automatic exactness of the analog controller or a guarantee that arbitrary grammars will be learned. Reported finite-length generalization and extracted-machine claims remain source-specific, and no benchmark result or independently reproduced training is curated here.
⚠️ Curated Limitations & Negative Results
- This record covers the fractional-symbol stack formulation inspected in the 1992 author manuscript, not every later neural pushdown automaton or all differentiable-stack architectures.
- Simulation thresholds have unspecified exact endpoints, and empty-stack, underflow and signed-action implementation details are not certified. No allocator or executable implementation was inspected.
- The stack-read sensitivity is an explicit approximation. Analog quantities and a recursive derivative expression do not certify a globally exact or smooth gradient computation.
- A zero illegal-string surrogate loss does not alone enforce the stronger categorical rejection alternatives stated in the source prose.
- Hints add grammar information; quantization is an additional extraction step. Selected small-language comparisons do not establish arbitrary-grammar learning or unlimited exact recognition.
- All six pages of the author-hosted conference manuscript were read. No later version, author code, training, runtime audit or empirical replication was inspected. Earlier work is acknowledged; historical priority is not asserted.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:RecurrentNeuralNetwork
Recurrent Neural Network
|
broad_match | NNPDA combines recurrent state dynamics with a particular external fractional stack and controller; the AIO target is the broader recurrent architecture category. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
das1992
|
Sreerupa Das, C. Lee Giles, Guo-Zheng Sun
|
primary paper
full_text
|
sha256:f9a7fe849cbc…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-13T05:59:13Z
Updated: 2026-10-13T05:59:13Z
Source File:
data/curated/NeuralNetworkPushdownAutomaton.yaml