Counting with Analog Neurons

0502583 - ÚI 2020 RIV CH eng C - Conference Paper (international conference)
Šíma, Jiří
Counting with Analog Neurons.
Artificial Neural Networks and Machine Learning – ICANN 2019: Theoretical Neural Computation. Proceedings, Part I. Cham: Springer, 2019 - (Tetko, I.; Kůrková, V.; Karpov, P.; Theis, F.), s. 389-400. Lecture Notes in Computer Science, 11727. ISBN 978-3-030-30486-7. ISSN 0302-9743.
[ICANN 2019. International Conference on Artificial Neural Networks /28./. Munich (DE), 17.09.2019-19.09.2019]
R&D Projects: GA ČR(CZ) GA19-05704S
Institutional support: RVO:67985807
Keywords : Neural computing * Analog state * Deterministic pushdown automaton * Deterministic context-free language * Chomsky hierarchy
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

We refine the analysis of binary-state neural networks with alpha extra analog neurons (alpha-ANNs). For rational weights, it has been known that online 1ANNs accept context-sensitive languages including examples of non-context-free languages, while offline 3ANNs are Turing complete. We now prove that the deterministic (context-free) language containing the words of n zeros followed by n ones, cannot be recognized offline by any 1ANN with real weights. Hence, the offline 1ANNs are not Turing complete. On the other hand, we show that any deterministic language can be accepted by a 2ANN with rational weights. Thus, two extra analog units can count to any number which is not the case of one analog neuron.
Permanent Link: http://hdl.handle.net/11104/0294486