Computational limitations of affine automata and generalized affine automata




Hirvensalo Mika, Moutot Etienne, Yakaryilmaz Abuzer

PublisherSPRINGER

2021

Natural Computing

NATURAL COMPUTING

NAT COMPUT

20

2

259

270

12

1567-7818

1572-9796

DOIhttps://doi.org/10.1007/s11047-020-09815-1

https://link.springer.com/article/10.1007/s11047-020-09815-1

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.

Last updated on 2024-26-11 at 10:41