| dbo:abstract
|
- 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. 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. (en)
- 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 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. (it)
- 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 *(TO ))(WRD *(TO ))(MEM *(TO ))(PUSH **(TO ))(VIR *(TO ))(JUMP *(POP ) część typów jest znana z RTN: CAT – kategoria np. rzeczownik, przymiotnikWRD – symbol terminalnyPUSH – zapamiętanie stanu przed przejściem do początku innego diagramu POP – odtworzenie pozycji ze stosuJUMP – przejścia bez żadnego symbolu terminalnego Dodatkowo: MEM – tak jak WRD z wyjątkiem tego, ze symbol musi należeć do listy 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 ) powoduje że rejestr przyjmuje wartość wyliczoną z (SETRQ ) bezpośrednio podstawia to (ADDL ) zamiast zastąpić wartość w rejestrze, wyliczona wartość dodawana jest do lewej strony listy(ADDR ) podobnie do ADDL tylko do prawej strony listy(SENDR ) wstępna akcja używana tylko dla krawędzi PUSH; ustawia rejestr na wartość na niższym poziomie rekurencji; efektem jest, że sieć niższego poziomu jest wołana niczym proceura z parametrem przesyłanym przeze SENDR(SENDRQ ) - tak się ma SENDR jak SETRQ do SETR(LIFTR ) różni się od SENDR w tym, że ustawia rejestr na wartość poziomu powyżej bieżącego(HOLD ) wkłada wskazane na listę HOLD jako element . Lista HOLD jest globalna, widzialna przez wszystkie poziomy, ta akcja działa razem z VIR(VERIFY ) drugi test dla gramatyka dla : (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. (pl)
- Расширенная сеть переходов (РСП; усиленная сеть переходов или УП-сеть) (англ. Augmented transition network, сокращённо — ATN) — технология грамматической и семантической обработки текстов, предложенная американским лингвистом Вудсом в 1970 (перевод статьи на русский опубликован в 1976 году). Расширенная сеть переходов представляет собой автомат, меняющий состояния при переходе от слова к слову в разбираемом предложении или тексте. Термин расширенная применительно к сетям переходов означает, что узлы сети наделены дополнительными условиями проверки, в которых могут содержаться различные согласовательные конструкции, а также команды, строящие выделенные из текста синтактико-смысловые конструкции. В силу фиксированности порядка слов в английском языке, РСП хорошо подходят для грамматико-семантического разбора текстов на английском языке (для чего и были разработаны изначально). Считается, что в силу произвольного порядка слов в русском языке, использование Расширенных сетей переходов для обработки русскоязычных текстов малоэффективно. Тем не менее существует несколько работ, посвященных использованию РСП для анализа текстов на русском языке. Так в работе при разборе предложений каждое слово анализируется с использованием морфологического парсера. Ребра графа, которым является РСП, размечены наборами морфологических признаков, подходящих для перехода по дуге, а узлы графа содержат команды для выделения найденных синтактико-семантических отношений. А в работе представлен метод порождения правил синтаксической сегментации применительно к набору Расширенных сетей переходов для разбора как англо- так и русскоязычных текстов. (ru)
|
| rdfs:comment
|
- 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. (en)
- 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. (it)
- 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. (pl)
- Расширенная сеть переходов (РСП; усиленная сеть переходов или УП-сеть) (англ. Augmented transition network, сокращённо — ATN) — технология грамматической и семантической обработки текстов, предложенная американским лингвистом Вудсом в 1970 (перевод статьи на русский опубликован в 1976 году). (ru)
|
