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
Lehti: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 nimiLecture 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.
