Skip to main navigation Skip to search Skip to main content

Computational Limitations of Affine Automata

  • Mika Hirvensalo*
  • , Etienne Moutot
  • , Abuzer Yakaryılmaz
  • *Corresponding author for this work
  • University of Turku
  • ENS de Lyon – CNRS – UCBL – Université de Lyon

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationUnconventional Computation and Natural Computation - 18th International Conference, UCNC 2019, Proceedings
EditorsShinnosuke Seki, Ian McQuillan
PublisherSpringer Verlag
Pages108-121
Number of pages14
ISBN (Print)9783030193102
DOIs
Publication statusPublished - 2019
Event18th International Conference on Unconventional Computation and Natural Computation, UCNC 2019 - Tokyo, Japan
Duration: 3 Jun 2019 → 7 Jun 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11493 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Unconventional Computation and Natural Computation, UCNC 2019
Country/TerritoryJapan
CityTokyo
Period3/06/19 → 7/06/19

Fingerprint

Dive into the research topics of 'Computational Limitations of Affine Automata'. Together they form a unique fingerprint.

Cite this