A4 Refereed article in a conference publication
Computational Limitations of Affine Automata
Authors: Hirvensalo M., Moutot E., Yakaryılmaz A.
Editors: Ian McQuillan, Shinnosuke Seki
Conference name: International Conference on Unconventional Computation and Natural Computation
Publisher: Springer Verlag
Publication year: 2019
Journal:Lecture Notes in Computer Science
Book title : Unconventional Computation and Natural Computation : 18th International Conference, UCNC 2019, Tokyo, Japan, June 3–7, 2019, Proceedings
Journal name in sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Series title: Lecture Notes in Computer Science
Volume: 11493
ISBN: 978-3-030-19310-2
eISBN: 978-3-030-19311-9
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-030-19311-9_10
We present two new results on the computational limitations of affine automata. First, we show that the computation of bounded-error rational-valued affine automata is simulated in logarithmic space. Second, we give an impossibility result for algebraic-valued affine automata. As a result, we identify some unary languages (in logarithmic space) that are not recognized by algebraic-valued affine automata with cutpoints.
