Augmented transition network

Una augmented transition network (ATN) è una tipologia di grafo usato per la definizione operazionale dei linguaggi formali, specialmente per quanto riguarda il parsing di lingue naturali relativamente complessi, ha ampia applicazione in intelligenza artificiale. Una ATN può, in teoria, analizzare la struttura di qualunque frase, anche se complicata.

Le ATN sono costruite sull'idea di utilizzare macchine a stati finiti (modello di Markov) per effettuare il parsing di parole. W. A. Woods in "Transition Network Grammars for Natural Language Analysis" indica che aggiungendo il meccanismo di ricorsione ad un modello a stati finiti, è possibile eseguire il parsing in maniera più efficiente. È realizzato un insieme di grafi di transizione invece di costruire un automa per una particolare frase. Una frase sintatticamente corretta è parsificata raggiungendo uno stato finale per ogni grafo. Le transizioni fra questi grafi sono semplici chiamate a funzioni da uno stato a uno stato iniziale di qualunque grafo nella rete. Si stabilisce se una frase è sintatticamente corretta se uno stato finale è raggiunto dall'ultima parola della frase.

Questo modello raggiunge molti obiettivi della natura del linguaggio in quanto cattura le regolarità del linguaggio. Ovvero, se è presente un processo che opera su diversi ambienti, la grammatica può incapsulare il processo in una singola struttura. Tale incapsulazione non semplifica solo la grammatica, ma ha il valore aggiunto dell'efficienza dell'operazione. Ulteriore vantaggio di tale modello si ha nell'abilità di rinviare la presa di decisioni. Molte grammatiche ipotizzano in presenza di ambiguità. Ciò significa che non si conosce al momento abbastanza sulla frase. Attraverso l'uso della ricorsione, le ATN risolvono tale inefficienza rinviando le decisioni sino a quando non si conosce abbastanza sulla frase.

Bibliografia

• 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.

Voci correlate

• linguaggio context free
• macchina a stati finiti
• grammatica formale
• Parsing
• Recursive transition network

Collegamenti esterni

• An introduction on ATNs by Paul Graham in On Lisp