Computational Limitations of Affine Automata




Hirvensalo M., Moutot E., Yakaryılmaz A.

Ian McQuillan, Shinnosuke Seki

International Conference on Unconventional Computation and Natural Computation

PublisherSpringer Verlag

2019

Lecture Notes in Computer Science

Unconventional Computation and Natural Computation : 18th International Conference, UCNC 2019, Tokyo, Japan, June 3–7, 2019, Proceedings

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Lecture Notes in Computer Science

11493

978-3-030-19310-2

978-3-030-19311-9

0302-9743

DOIhttps://doi.org/10.1007/978-3-030-19311-9_10(external)



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.



Last updated on 2024-26-11 at 13:01