Number of the records: 1
Subrecursive Neural Networks
- 1.0490203 - ÚI 2020 RIV GB eng J - Journal Article
Šíma, Jiří
Subrecursive Neural Networks.
Neural Networks. Roč. 116, August (2019), s. 208-223. ISSN 0893-6080. E-ISSN 1879-2782
R&D Projects: GA ČR(CZ) GA19-05704S
Institutional support: RVO:67985807
Keywords : recurrent neural network * Chomsky hierarchy * cut language * quasi-periodic number
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 5.535, year: 2019
Method of publishing: Limited access
http://dx.doi.org/10.1016/j.neunet.2019.04.019
It has been known for discrete-time recurrent neural networks (NNs) that binary-state models using the Heaviside activation function (with Boolean outputs 0 or 1) are equivalent to finite automata (level 3 in the Chomsky hierarchy), while analog-state NNs with rational weights, employing the saturated-linear function (with real-number outputs in the interval ), are Turing complete (Chomsky level 0) even for three analog units. However, it is as yet unknown whether there exist subrecursive (i.e. sub-Turing) NN models which occur on Chomsky levels 1 or 2. In this paper, we provide such a model which is a binary-state NN extended with one extra analog unit (1ANN). We achieve a syntactic characterization of languages that are accepted online by 1ANNs in terms of so-called cut languages which are combined in a certain way by usual operations. We employ this characterization for proving that languages accepted by 1ANNs with rational weights are context-sensitive (Chomsky level 1) and we present explicit examples of such languages that are not context-free (i.e. are above Chomsky level 2). In addition, we formulate a sufficient condition when a 1ANN recognizes a regular language (Chomsky level 3) in terms of quasi-periodicity of parameters derived from its real weights, which is satisfied e.g. for rational weights provided that the inverse of the real self-loop weight of the analog unit is a Pisot number.
Permanent Link: http://hdl.handle.net/11104/0284481
File Download Size Commentary Version Access 0490203-sub.pdf 5 2 MB Author´s preprint open-access 0490203-aa.pdf 13 1 MB Publisher’s postprint require
Number of the records: 1