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

An ATN for parsing noun phrases.^{[2]: Fig. 6(a)}

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

An ATN for parsing questions about travel budgets.^{[2]: Fig. 6(b)}

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:

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

See also

• Context free language
• Formal grammar
• Parsing
• Recursive transition network