A1 Refereed original research article in a scientific journal
Computational limitations of affine automata and generalized affine automata
Authors: Hirvensalo Mika, Moutot Etienne, Yakaryilmaz Abuzer
Publisher: SPRINGER
Publication year: 2021
Journal: Natural Computing
Journal name in source: NATURAL COMPUTING
Journal acronym: NAT COMPUT
Volume: 20
Issue: 2
First page : 259
Last page: 270
Number of pages: 12
ISSN: 1567-7818
eISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-020-09815-1
Web address : https://link.springer.com/article/10.1007/s11047-020-09815-1
Self-archived copy’s web address: 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.
Downloadable publication This is an electronic reprint of the original article. |  |
