A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Computational limitations of affine automata and generalized affine automata
Tekijät: Hirvensalo Mika, Moutot Etienne, Yakaryilmaz Abuzer
Kustantaja: SPRINGER
Julkaisuvuosi: 2021
Journal: Natural Computing
Tietokannassa oleva lehden nimi: NATURAL COMPUTING
Lehden akronyymi: NAT COMPUT
Vuosikerta: 20
Numero: 2
Aloitussivu: 259
Lopetussivu: 270
Sivujen määrä: 12
ISSN: 1567-7818
eISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-020-09815-1
Verkko-osoite: https://link.springer.com/article/10.1007/s11047-020-09815-1
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/53064922
We present new results on the computational limitations of affine automata (AfAs). First, we show that using the endmarker does not increase the computational power of AfAs. Second, we show that the computation of bounded-error rational-valued AfAs can be simulated in logarithmic space. Third, we identify some logspace unary languages that are not recognized by algebraic-valued AfAs. Fourth, we show that using arbitrary real-valued transition matrices and state vectors does not increase the computational power of AfAs in the unbounded-error model. When focusing only the rational values, we obtain the the same result also for bounded error. As a consequence, we show that the class of bounded-error affine languages remains the same when the AfAs are restricted to use rational numbers only.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
