A4 Refereed article in a conference publication

Computational Limitations of Affine Automata




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

EditorsIan McQuillan, Shinnosuke Seki

Conference nameInternational Conference on Unconventional Computation and Natural Computation

PublisherSpringer Verlag

Publication year2019

JournalLecture 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 titleLecture Notes in Computer Science

Volume11493

ISBN978-3-030-19310-2

eISBN978-3-030-19311-9

ISSN0302-9743

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


Abstract

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