Augmented transition network

An augmented transition network or ATN is a type of graph theoretic structure used in the operational definition of formal languages, used especially in parsing relatively complex natural languages, and having wide application in artificial intelligence. An ATN can, theoretically, analyze the structure of any sentence, however complicated. ATN are modified transition networks and an extension of RTNs^{[citation needed]}.

ATNs build on the idea of using finite-state machines (Markov model) to parse sentences. W. A. Woods in "Transition Network Grammars for Natural Language Analysis" claims that by adding a recursive mechanism to a finite state model, parsing can be achieved much more efficiently. Instead of building an automaton for a particular sentence, a collection of transition graphs are built. A grammatically correct sentence is parsed by reaching a final state in any state graph. Transitions between these graphs are simply subroutine calls from one state to any initial state on any graph in the network. A sentence is determined to be grammatically correct if a final state is reached by the last word in the sentence.

This model meets many of the goals set forth by the nature of language in that it captures the regularities of the language. That is, if there is a process that operates in a number of environments, the grammar should encapsulate the process in a single structure. Such encapsulation not only simplifies the grammar, but has the added bonus of efficiency of operation. Another advantage of such a model is the ability to postpone decisions. Many grammars use guessing when an ambiguity comes up. This means that not enough is yet known about the sentence. By the use of recursion, ATNs solve this inefficiency by postponing decisions until more is known about a sentence.

Example

An augmented transition network for parsing noun phrases. The diagrams depict two ATNs used by the Bolt Beranek and Newman (BBN) "Hear-What-I-Mean" (HWIM) speech-understanding system^[1] of the mid-1970s, produced for ARPA's Speech Understanding Research project in the 1970s.^[2] It was intended to parse sentences that are questions about travel budgets, like "What is the plane fare to Ottawa?".

ATNs are finite-state graphs whose arcs may perform tests (e.g. part-of-speech checks) and actions (e.g. pushing or popping a subsidiary network).

In the diagram:

Every state is a node, and every arc is a labelled arrow. A double-circled state is the start state.
Lexical or category tests appear on the arc label like CAT DET.
Procedural actions appear on the arc label like PUSH PP/ or POP.
A tiny tree fragment to the right illustrates the structure that will be returned to the calling ATN after the POP.

Generic noun-phrase ATN

This ATN recognizes (or generates) some English noun phrases.

Step	Arc traversed	Effect on parse / stack
1	`CAT DET` or `JUMP` from `NP/` to `NP/DET`	Reads an optional determiner such as "the", "a", "an".
2	`CAT ADJ` self-loop at `NP/DET`	Reads 0 or more adjectives ("big", "red", "Victorian"…).
3	`CAT N`	Reads the head noun (e.g. "house").
4	`PUSH PP/` self-loop at `NP/N`	Parses 0 or more PP; e.g. "on the hill", each time by calling on another ATN. Control returns to `NP/N` after each PP is parsed.
5	`POP`	Pops the entire stack, shown as the labelled tree: root `NP` daughters `DET`, `ADJ`, `N`, `PP`

The graph therefore parses sequences such as:

\[DET the] \[ADJ big] \[N house] \[PP on the hill]

where the \[PP on the hill] would have more structure inside it, illustrated by the small triangle beneath the output PP.

Trip-specific noun-phrase ATN

This ATN is a variant specialized for parsing sentences that are about travel. It inherits the generic pattern but hard-codes trip-related words and adjuncts.

Step	Arc traversed	Interpretation
1	`CAT DET` or `JUMP` (`TRIP/` → `T/DET`)	Optional determiner ("a", "the").
2	Loop on `CAT TRIP-ADJ`	Consumes 0 or more trip-specific adjectives ("cheap", "round-trip"…).
3	`WRD TRIP, TRIP-S` (`T/DET` → `T/TRIP`)	Consumes 1 of the literal words "trip" or "trips".
4	`PUSH DATE/` on `T/TRIP`	Consumes 0 or more temporal modifiers ("on Monday", "next week"…) by calling on other ATNs.
5	`WRD TO` followed by `PUSH PLACE/` or `PUSH MEETING/`	Parses destination or meeting-place phrases ("to Paris", "to the conference"…) by calling on other ATNs to parse `PLACE` or MEETING.
6	`WRD BY` followed by `CAT PRO-OBJ` or `PUSH PEOPLE/`	Parses agent phrase ("by Tom", "by the organiser") either as a proper object, or by calling on another ATN that parses `PEOPLE`.
7	`POP`	Pops the entire stack, shown as the labelled tree.

A complete generation trace for "a cheap trip to Paris by Tom" is therefore:

Start at TRIP/ and read determiner "a".
Loop once on CAT TRIP-ADJ to accept "cheap".
Consume "trip" via WRD TRIP.
Read keyword "to".
Push the PLACE/ network, yielding "Paris".
Encounter "by", switch to state T/BY, then accept the proper-object "Tom".
Pop, returning the fully-expanded NP subtree.

References

^ Woods, W.A.; Bates, M.; Brown, G.; Bruce, B.; Cook, C.; Klovstad, J.; Makhoul, J.; Nash-Webber, B.; Schwartz, R.; Wolf, J.; Zue, V. (1976). Speech Understanding Systems: Final Technical Progress Report, Volumes I-V (BBN Technical Report). Cambridge, MA: Bolt Beranek and Newman Inc. OCLC 4173925. 3848.
^ ^a ^b ^c Klatt, Dennis H. (1977-12-01). "Review of the ARPA Speech Understanding Project". The Journal of the Acoustical Society of America. 62 (6): 1345–1366. doi:10.1121/1.381666. ISSN 0001-4966.

Woods, William A (1970). "Transition Network Grammars for Natural Language Analysis" (PDF). Communications of the ACM. 13 (10): 591–606. doi:10.1145/355598.362773.
Wanner, Eric; Maratsos, Michael (1978). "An ATN approach to comprehension". In M. Halle; J. Bresnan; G.A. Miller (eds.). Linguistic Theory and Psychological Reality. Cambridge: MIT Press.
Wanner, Eric (1980). "The ATN and the Sausage Machine: which one is baloney?". Cognition. 8 (2): 209–225. doi:10.1016/0010-0277(80)90013-X. ISSN 0010-0277. PMID 7389289.
Winograd, Terry (1983). Language as a Cognitive Process, Volume 1: Syntax. Reading, MA: Addison–Wesley. OCLC 4434039783. OSTI 5673189.