Exact Affine Counter Automata

We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown auto...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2022-04, Vol.33 (3n04), p.349-370
Main Authors: Nakanishi, Masaki, Khadiev, Kamil, Prusis, Krisjanis, Vihrovs, Jevgenijs, Yakaryılmaz, Abuzer
Format: Article
Language:English
Subjects:
Algorithms
Languages
Polynomials
Real time
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k -counter automata. Then, we show that exact realtime affine counter automata can recognize a family of regular languages with a few states but the states required by realtime deterministic k -counter automata cannot be bounded. We also show that stateless affine increment-only counter automata can recognize some nonregular languages with one-sided bounded-error. Moreover, we show that a promise problem not solved by two-way quantum finite automata in polynomial time can be solved by Las Vegas affine finite automata. Lastly, we present an affine finite automaton algorithm using a counter cleverly to recognize a language, for which we do not know any bounded-error affine finite automata or two-way quantum finite automata recognizing it.
ISSN:0129-0541
1793-6373
DOI:10.1142/S012905412241009X