6533b86efe1ef96bd12cc841

RESEARCH PRODUCT

Computational Limitations of Affine Automata

Abuzer YakaryilmazMika HirvensaloEtienne Moutot

subject

FOS: Computer and information sciencesDiscrete mathematics050101 languages & linguisticsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESUnary operationFormal Languages and Automata Theory (cs.FL)Computer scienceComputation05 social sciencesComputer Science - Formal Languages and Automata Theory02 engineering and technology[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Nonlinear Sciences::Cellular Automata and Lattice GasesLogarithmic spaceAutomatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processing0501 psychology and cognitive sciencesAffine transformationImpossibilityComputer Science::Formal Languages and Automata TheoryComputingMilieux_MISCELLANEOUS

description

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.

yearjournalcountryeditionlanguage
2019-06-03
10.1007/978-3-030-19311-9_10https://hal.archives-ouvertes.fr/hal-02157985