Augmented Transition Networks (1970) › The Solution: Networks with Memory and Procedural Arcs

An ATN combined recursive network calls with mutable registers. Code attached to an arc could inspect the next input item and the current register state. If its conditions passed, the code could consume input, update state, or construct part of the result.

A basic ATN consisted of a set of networks, each corresponding to a grammatical category like sentence, noun phrase, verb phrase, or prepositional phrase. Each network was a directed graph with nodes (states) and arcs (transitions). The parser began in an initial state and tried to follow arcs to reach a final state. But unlike finite-state machines, ATN arcs could contain conditions that had to be satisfied before the transition could occur, and actions that modified registers when the transition was taken.

Registers provided memory during parsing. They could store information about words or phrases that had been parsed: syntactic categories, semantic features, or partial syntactic structures. For example, when parsing a noun phrase, the ATN might store the determiner in one register, the head noun in another, and any adjectives in yet another. Later transitions could test the contents of these registers to guide parsing decisions. Registers allowed ATNs to build up representations incrementally and to use information from earlier in the parse to guide later choices.

Recursive network calls handled nested structures. When an ATN parser processing a sentence encountered what appeared to be a noun phrase, it could call the noun phrase network as a subroutine. That network would attempt to parse a noun phrase from the current position. If successful, it would return control to the calling network along with the parsed structure, and the parser would continue from where the noun phrase ended. This recursive mechanism allowed ATNs to handle arbitrarily deep nesting without explicitly enumerating all possible structures.

The recursion mechanism used a push-down stack, similar to recursive function calls in programming languages. When a network called another network, it pushed its current state onto the stack. When the called network finished (either successfully or by failing), it popped the stack to return control. This stack-based recursion enabled ATNs to parse structures like "the cat on the mat in the room on the first floor of the building," with each prepositional phrase containing another prepositional phrase.

Transitions in an ATN could perform tests before being taken and actions when taken. A test might check whether the current word belonged to a particular category: "Is the next word a determiner?" or "Is the next word a verb?" Actions could set registers: "Store the current word as the subject" or "Add this adjective to the modifier list." Tests and actions allowed ATNs to incorporate linguistic knowledge directly into the parsing process, making parsing sensitive to context and accumulated information.

A simple example illustrates how these mechanisms worked together. Consider an ATN for parsing noun phrases. The network might start in an initial state and have an arc labeled with a test "word is a determiner" leading to another state. When that transition was taken, an action might set a register: "determiner-register := current word." From the new state, there might be an optional arc (indicated by a jump) that could be taken if the next word was an adjective, with an action adding that adjective to an adjective list. Then there would be a transition requiring a noun, with an action storing that noun as the head. Finally, an optional recursive call to the prepositional phrase network could attach prepositional phrase modifiers.

When parsing "the big black cat," the ATN would store "the" in the determiner register, add "big" and "black" to the adjective list, store "cat" as the head noun, and construct a noun phrase structure from these components. When parsing "the cat on the mat," after parsing "the cat," it would call the prepositional phrase network recursively. That network would parse "on the mat," which itself contains a noun phrase "the mat," requiring another recursive call. The recursion would unwind, returning structures up the call stack until the complete parse was assembled.

Multiple arcs could leave one state, giving the parser alternative analyses. A depth-first interpreter might try one path and backtrack after failure. Tests on arcs could prune an alternative using accumulated features or a domain-specific interpretation, although a mistaken early test could also discard a valid parse.