2019/04/04 by Hirvensalo, Mika, Moutot, Etienne, Yakaryılmaz, Abuzer
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1904.02428
We present two new results on the computational limitations of affine automata. First, we show that the computation of bounded-error rational-values 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.