Przyrostowa sieć przejść

Przyrostowa sieć przejść (ang. Augmented Transition Network, ATN) zwana czasem uogólnioną siecią przejść stanowi rozszerzenie RTN.

Sieci te używane są najczęściej w analizie języków naturalnych. Również w algorytmie parsera LL(*). Jest postaci grupy grafów, gdzie przechodzimy z jednego stanu sieci do następnego przez etykietowaną krawędź. Oprócz etykiet występujących w RTN, z których najważniejsze to PUSH i POP, krawędź ma przypisany warunek, który musi być spełniony, aby móc tą krawędzią przejść oraz akcje do wykonania. Sieć poza tym wyposażona jest w rejestry, gdzie trzymane są wartości, które potem mogą być poddawane badaniu przez procedury testujące oraz ustawiane przez akcje.

Dzięki temu może równoważna jest mocą maszynie Turinga.

Jak podaje Bates łuki mogą być typów:

(CAT <category> <test> <action>*(TO <next state>))

(WRD <word> <test> <action>*(TO <next state>))

(MEM <list> <test> <action>*(TO <next state>))

(PUSH <state> <test> <pre-action>*<action>*(TO <next state>))

(VIR <constit-type> <test> <action>*(TO <next state>))

(JUMP <next state> <test> <action>*

(POP <form> <test>)

część typów jest znana z RTN:

CAT – kategoria np. rzeczownik, przymiotnik

WRD – symbol terminalny

PUSH – zapamiętanie stanu przed przejściem do początku innego diagramu <state>

POP – odtworzenie pozycji ze stosu

JUMP – przejścia bez żadnego symbolu terminalnego

Dodatkowo:

MEM – tak jak WRD z wyjątkiem tego, ze symbol musi należeć do listy <list>

VIR sprawdza, czy jakaś akcja przy wcześniejszej krawędzi nie umieściła nic na globalnej liście HOLD, jeśli tak – element jest usuwany z listy i wykonywane jest przejście.

Akcje:

(SETR <reg> <form>) powoduje że rejestr <reg> przyjmuje wartość wyliczoną z <form>

(SETRQ <reg> <value>) bezpośrednio podstawia <value> to <reg>

(ADDL <reg> <form>) zamiast zastąpić wartość w rejestrze, wyliczona wartość <form> dodawana jest do lewej strony listy

(ADDR <reg> <form>) podobnie do ADDL tylko do prawej strony listy

(SENDR <reg> <form>) wstępna akcja używana tylko dla krawędzi PUSH; ustawia rejestr <reg> na wartość <form> na niższym poziomie rekurencji; efektem jest, że sieć niższego poziomu jest wołana niczym proceura z parametrem przesyłanym przeze SENDR

(SENDRQ <reg> <value>) - tak się ma SENDR jak SETRQ do SETR

(LIFTR <reg> <form>) różni się od SENDR w tym, że ustawia rejestr na wartość <form> poziomu powyżej bieżącego

(HOLD <constit-type> <form>) wkłada wskazane <form> na listę HOLD jako element <constit-type>. Lista HOLD jest globalna, widzialna przez wszystkie poziomy, ta akcja działa razem z VIR

(VERIFY <form>) drugi test dla <form>

gramatyka dla $a^{n}b^{n}c^{n}$ :

 (defatn anbncn
       (abc (wrd a t (hold 'a 'a) (to abc/a)))
       (abc/a (wrd b t (to abc/b))
               (push abc t (to abc/ab)))
       (abc/ab (wrd c t (to abc/abc)))
       (abc/abc (pop t))
       (abc/b (vir a t (to abc/ba)))
       (abc/ba (wrd c t (to abc/abc))
               (wrd b t (to abc/b))))

Składnia opisu przypomina Lisp czy Clojure.