A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Computational Limitations of Affine Automata
Tekijät: Hirvensalo M., Moutot E., Yakaryılmaz A.
Toimittaja: Ian McQuillan, Shinnosuke Seki
Konferenssin vakiintunut nimi: International Conference on Unconventional Computation and Natural Computation
Kustantaja: Springer Verlag
Julkaisuvuosi: 2019
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Unconventional Computation and Natural Computation : 18th International Conference, UCNC 2019, Tokyo, Japan, June 3–7, 2019, Proceedings
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 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.
