Augmented transition network

Augmented transition network

An augmented transition network (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.

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.

References

* Winograd, Terry (1983), "Language as a Cognitive Process, Volume 1: Syntax", Addison–Wesley, Reading, MA.
* Woods, William A. (1970), "Transition Network Grammars for Natural Language Analysis", "Communications of the ACM" 13:10 (1970), 591–606.

ee also

* [http://aclweb.org/aclwiki/index.php?title=Augmented_Syntax_Diagram Augmented syntax diagram]
* Context free language
* Finite state machine
* Formal grammar
* Parsing
* Recursive transition network

External links

* [http://www.bookshelf.jp/texi/onlisp/onlisp_24.html#SEC141 An introduction on ATNs by Paul Graham in On_Lisp]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Recursive transition network — A recursive transition network ( RTN ) is a graph theoretical schematic used to represent the rules of a context free grammar. RTNs have application to programming languages, natural language and lexical analysis. Any sentence that is constructed …   Wikipedia

  • Presidential transition of Barack Obama — Obama–Biden Transition Project President …   Wikipedia

  • Artificial neural network — An artificial neural network (ANN), usually called neural network (NN), is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an… …   Wikipedia

  • ATN — comp. abbr. Augmented Transition Network abbr. Augmented Transition Network …   United dictionary of abbreviations and acronyms

  • Flowchart — A flowchart is a schematic representation of an algorithm or a stepwise process, showing the steps as boxes of various kinds, and their order by connecting these with arrows. Flowcharts are used in designing or documenting a process or program.… …   Wikipedia

  • ATN (disambiguation) — ATN may refer to: *Access Television Network *Action Performance Companies (stock symbol) *Acute tubular necrosis *Aeronautical telecommunications network *Air Tahiti Nui *ICAO code for Air Transport International * Anniston (Amtrak station),… …   Wikipedia

  • SNePS — is a knowledge representation, reasoning, and acting (KRRA) system developed and maintained by Stuart C. Shapiro and colleagues at the State University of New York at Buffalo. SNePS is simultaneously a logic based, frame based, and network based… …   Wikipedia

  • Natural language understanding — Learning to read by Sigurður málari, 19th century. Natural language understanding is a subtopic of natural language processing in artificial intelligence that deals with machine reading comprehension. The proc …   Wikipedia

  • ATN — acute tubular necrosis; Adolescent Trials Network; augmented transition network …   Medical dictionary

  • ATN — • acute tubular necrosis; • Adolescent Trials Network; • augmented transition network …   Dictionary of medical acronyms & abbreviations

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”