pith. sign in

arxiv: 1612.01870 · v1 · pith:C5LAG4OPnew · submitted 2016-12-06 · 💻 cs.FL

On the computational power of affine automata

classification 💻 cs.FL
keywords affineafasautomatacomputationalerrorlanguagepowerrecognized
0
0 comments X
read the original abstract

We investigate the computational power of affine automata (AfAs) introduced in [4]. In particular, we present a simpler proof for how to change the cutpoint for any affine language and a method how to reduce error in bounded error case. Moreover, we address to the question of [4] by showing that any affine language can be recognized by an AfA with certain limitation on the entries of affine states and transition matrices. Lastly, we present the first languages shown to be not recognized by AfAs with bounded-error.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.