The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
No campo da psicologia cognitiva, redes recorrentes simples são utilizadas para modelar o processamento da linguagem natural no cérebro humano. Por exemplo, Elman mostrou experimentalmente que as redes recorrentes simples podem prever a palavra mais à direita nas formas sentenciais de uma gramática específica, o que pode gerar sentenças compostas com alta probabilidade. Em relação a estes resultados, é natural perguntar se a capacidade computacional das redes recorrentes simples é suficiente para reconhecer linguagens naturais. Neste artigo, assumimos que o intervalo de uma função calculada em cada porta de uma rede recorrente simples é um conjunto finito. Esta é uma suposição bastante realista, porque não podemos implementar fisicamente uma porta cujo alcance seja um conjunto infinito. Em seguida, definimos relações de equivalência entre redes recorrentes simples e máquinas Mealy ou máquinas Moore, que são autômatos finitos com saída. Então, sob nossa suposição, mostramos (1) uma construção de uma máquina Mealy que simula uma dada rede recorrente simples, e (2) uma construção de uma rede recorrente simples que simula uma dada máquina de Moore. A partir destas duas construções, podemos concluir que a capacidade computacional das redes recorrentes simples é igual à dos autômatos finitos com saída sob nossa suposição.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Junnosuke MORIYA, Tetsuro NISHINO, "Relationships between the Computational Capabilities of Simple Recurrent Networks and Finite Automata" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 5, pp. 1184-1194, May 2001, doi: .
Abstract: In the filed of cognitive psychology, simple recurrent networks are used for modeling the natural language processing in the human brain. For example, Elman experimentally showed that the simple recurrent networks can predict the right-most word in sentential forms of a particular grammar which can generate compound sentences with high probability. Concerning these results, it is natural to ask whether the computational capability of the simple recurrent networks is sufficient to recognize natural languages. In this paper, we assume that the range of a function computed at each gate of a simple recurrent network is a finite set. This is a quite realistic assumption, because we cannot physically implement a gate whose range is an infinite set. Then, we define equivalence relations between simple recurrent networks and Mealy machines or Moore machines, which are finite automata with output. Then, under our assumption, we show (1) a construction of a Mealy machine which simulates a given simple recurrent network, and (2) a construction of a simple recurrent network which simulates a given Moore machine. From these two constructions, we can conclude that the computational capability of the simple recurrent networks is equal to that of finite automata with output under our assumption.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_5_1184/_p
Copiar
@ARTICLE{e84-a_5_1184,
author={Junnosuke MORIYA, Tetsuro NISHINO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Relationships between the Computational Capabilities of Simple Recurrent Networks and Finite Automata},
year={2001},
volume={E84-A},
number={5},
pages={1184-1194},
abstract={In the filed of cognitive psychology, simple recurrent networks are used for modeling the natural language processing in the human brain. For example, Elman experimentally showed that the simple recurrent networks can predict the right-most word in sentential forms of a particular grammar which can generate compound sentences with high probability. Concerning these results, it is natural to ask whether the computational capability of the simple recurrent networks is sufficient to recognize natural languages. In this paper, we assume that the range of a function computed at each gate of a simple recurrent network is a finite set. This is a quite realistic assumption, because we cannot physically implement a gate whose range is an infinite set. Then, we define equivalence relations between simple recurrent networks and Mealy machines or Moore machines, which are finite automata with output. Then, under our assumption, we show (1) a construction of a Mealy machine which simulates a given simple recurrent network, and (2) a construction of a simple recurrent network which simulates a given Moore machine. From these two constructions, we can conclude that the computational capability of the simple recurrent networks is equal to that of finite automata with output under our assumption.},
keywords={},
doi={},
ISSN={},
month={May},}
Copiar
TY - JOUR
TI - Relationships between the Computational Capabilities of Simple Recurrent Networks and Finite Automata
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1184
EP - 1194
AU - Junnosuke MORIYA
AU - Tetsuro NISHINO
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2001
AB - In the filed of cognitive psychology, simple recurrent networks are used for modeling the natural language processing in the human brain. For example, Elman experimentally showed that the simple recurrent networks can predict the right-most word in sentential forms of a particular grammar which can generate compound sentences with high probability. Concerning these results, it is natural to ask whether the computational capability of the simple recurrent networks is sufficient to recognize natural languages. In this paper, we assume that the range of a function computed at each gate of a simple recurrent network is a finite set. This is a quite realistic assumption, because we cannot physically implement a gate whose range is an infinite set. Then, we define equivalence relations between simple recurrent networks and Mealy machines or Moore machines, which are finite automata with output. Then, under our assumption, we show (1) a construction of a Mealy machine which simulates a given simple recurrent network, and (2) a construction of a simple recurrent network which simulates a given Moore machine. From these two constructions, we can conclude that the computational capability of the simple recurrent networks is equal to that of finite automata with output under our assumption.
ER -