6533b873fe1ef96bd12d453d

RESEARCH PRODUCT

On the computational power of affine automata

Abuzer YakaryilmazMika HirvensaloMika HirvensaloEtienne Moutot

subject

Discrete mathematicsFOS: Computer and information sciencesComputer scienceFormal Languages and Automata Theory (cs.FL)Computer Science - Formal Languages and Automata Theory0102 computer and information sciences02 engineering and technologyerror reduction[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]01 natural sciencesBounded errorPower (physics)Automatonaffine automata[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringnon-classical models of automatacutpoint languages020201 artificial intelligence & image processingTransition matricesAffine transformationcompact setsbounded error

description

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.

yearjournalcountryeditionlanguage
2017-03-06
10.1007/978-3-319-53733-7_30https://hal.science/hal-01908682