Computational Limitations of Affine Automata

被引：3
作者：
Hirvensalo, Mika [1 ]
Moutot, Etienne [1 ,2 ]
Yakaryilmaz, Abuzer [3 ]
机构：
[1] Univ Turku, Dept Math & Stat, Turku 20014, Finland
[2] Univ Lyon, Ecole Normale Super Lyon, CNRS, LIP,ENS Lyon,UCBL, Lyon, France
[3] Univ Latvia, Ctr Quantum Comp Sci, Fac Comp, Riga, Latvia
来源：
UNCONVENTIONAL COMPUTATION AND NATURAL COMPUTATION, UCNC 2019 | 2019年 / 11493卷
关键词：
LANGUAGES;
D O I：
10.1007/978-3-030-19311-9_10
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We present two new results on the computational limitations of affine automata. First, we show that the computation of bounded-error rational-valued 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.
引用
收藏
页码：108 / 121
页数：14
相关论文
共 18 条
  • [1] Algebraic results on quantum automata
    Ambainis, A
    Beaudry, M
    Golovkins, M
    Kikusts, A
    Mercer, M
    Thérien, D
    [J]. THEORY OF COMPUTING SYSTEMS, 2006, 39 (01) : 165 - 188
  • [2] Ambainis A., 2015, CORR
  • [3] [Anonymous], 1996, INTRO THEORY COMPUTA
  • [4] Affine Computation and Affine Automaton
    Diaz-Caro, Alejandro
    Yakaryilmaz, Abuzer
    [J]. COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2016, 2016, 9691 : 146 - 160
  • [5] EVERTSE JH, 1984, COMPOS MATH, V53, P225
  • [6] A SIMPLE DEMONSTRATION OF THE SKOLEM-MAHLER-LECH THEOREM
    HANSEL, G
    [J]. THEORETICAL COMPUTER SCIENCE, 1986, 43 (01) : 91 - 98
  • [7] On the Computational Power of Affine Automata
    Hirvensalo, Mika
    Moutot, Etienne
    Yakaryilmaz, Abuzer
    [J]. LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2017), 2017, 10168 : 405 - 417
  • [8] Error-Free Affine, Unitary, and Probabilistic OBDDs
    Ibrahimov, Rishat
    Khadiev, Kamil
    Prusis, Krisjanis
    Yakaryilmaz, Abuzer
    [J]. DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2018, 2018, 10952 : 175 - 187
  • [9] Jeandel E, 2007, THEOR COMPUT SYST, V40, P397, DOI [10.1007/s00224-006-1314-y, 10.1007/s00224-006-l314-y]
  • [10] On the power of quantum finite state automata
    Kondacs, A
    Watrous, J
    [J]. 38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, : 66 - 75
12