Computational limitations of affine automata and generalized affine automata

• DOI: 10.1007/s11047-020-09815-1
• Publication Date: 2021-01-18T13:07:19Z
• Authors: Mika Hirvensalo; Etienne Moutot; Abuzer Yakaryılmaz
• Keywords: Unary operation; Theory of computation

Abstract We present new results on the computational limitations of affine automata (AfAs). First, we show that using endmarker does not increase power AfAs. Second, computation bounded-error rational-valued AfAs can be simulated in logarithmic space. Third, identify some logspace unary languages are recognized by algebraic-valued Fourth, arbitrary real-valued transition matrices and state vectors unbounded-error model. When focusing only rational values, obtain same result also for bounded error. As a consequence, class remains when restricted to use numbers only.