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!
cited_by
cites cdi_FETCH-LOGICAL-c262X-1d90aba7f685f94afbbf5b424e6785c8e76b6d786748acb23db7fe3a30f2dde83
container_end_page 370
container_issue 3n04
container_start_page 349
container_title International journal of foundations of computer science
container_volume 33
creator Nakanishi, Masaki
Khadiev, Kamil
Prusis, Krisjanis
Vihrovs, Jevgenijs
Yakaryılmaz, Abuzer
description 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.
doi_str_mv 10.1142/S012905412241009X
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2666760153</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2666760153</sourcerecordid><originalsourceid>FETCH-LOGICAL-c262X-1d90aba7f685f94afbbf5b424e6785c8e76b6d786748acb23db7fe3a30f2dde83</originalsourceid><addsrcrecordid>eNplkEtLw0AcxBdRMNR-AA9CwHN0n_9NjiHUBxQ8qNDbsk-ItEndTVC_vQkRLz3NYeY3A4PQNcF3hHB6_4oJrbDghFJOMK52ZygjsmIFMMnOUTbbxexfonVKrcGkAiaogAzdbL61HfI6hLbzedOP3eBjXo9Df9CDvkIXQe-TX__pCr0_bN6ap2L78vjc1NvCUqC7grgKa6NlgFKEiutgTBCGU-5BlsKWXoIBJ0uQvNTWUOaMDJ5phgN1zpdshW6X3mPsP0efBvXRj7GbJhUFAAmYCDalyJKysU8p-qCOsT3o-KMIVvMR6uSIicEL89XHvUu29d3Qhtb-o6fIL3nOXiU</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2666760153</pqid></control><display><type>article</type><title>Exact Affine Counter Automata</title><source>World Scientific Journals【Remote access available】</source><creator>Nakanishi, Masaki ; Khadiev, Kamil ; Prusis, Krisjanis ; Vihrovs, Jevgenijs ; Yakaryılmaz, Abuzer</creator><creatorcontrib>Nakanishi, Masaki ; Khadiev, Kamil ; Prusis, Krisjanis ; Vihrovs, Jevgenijs ; Yakaryılmaz, Abuzer</creatorcontrib><description>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.</description><identifier>ISSN: 0129-0541</identifier><identifier>EISSN: 1793-6373</identifier><identifier>DOI: 10.1142/S012905412241009X</identifier><language>eng</language><publisher>Singapore: World Scientific Publishing Company</publisher><subject>Algorithms ; Languages ; Polynomials ; Real time</subject><ispartof>International journal of foundations of computer science, 2022-04, Vol.33 (3n04), p.349-370</ispartof><rights>2022, World Scientific Publishing Company</rights><rights>2022. World Scientific Publishing Company</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c262X-1d90aba7f685f94afbbf5b424e6785c8e76b6d786748acb23db7fe3a30f2dde83</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.worldscientific.com/doi/reader/10.1142/S012905412241009X$$EPDF$$P50$$Gworldscientific$$H</linktopdf><link.rule.ids>314,780,784,3213,4872,27924,27925,55587</link.rule.ids></links><search><creatorcontrib>Nakanishi, Masaki</creatorcontrib><creatorcontrib>Khadiev, Kamil</creatorcontrib><creatorcontrib>Prusis, Krisjanis</creatorcontrib><creatorcontrib>Vihrovs, Jevgenijs</creatorcontrib><creatorcontrib>Yakaryılmaz, Abuzer</creatorcontrib><title>Exact Affine Counter Automata</title><title>International journal of foundations of computer science</title><description>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.</description><subject>Algorithms</subject><subject>Languages</subject><subject>Polynomials</subject><subject>Real time</subject><issn>0129-0541</issn><issn>1793-6373</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><recordid>eNplkEtLw0AcxBdRMNR-AA9CwHN0n_9NjiHUBxQ8qNDbsk-ItEndTVC_vQkRLz3NYeY3A4PQNcF3hHB6_4oJrbDghFJOMK52ZygjsmIFMMnOUTbbxexfonVKrcGkAiaogAzdbL61HfI6hLbzedOP3eBjXo9Df9CDvkIXQe-TX__pCr0_bN6ap2L78vjc1NvCUqC7grgKa6NlgFKEiutgTBCGU-5BlsKWXoIBJ0uQvNTWUOaMDJ5phgN1zpdshW6X3mPsP0efBvXRj7GbJhUFAAmYCDalyJKysU8p-qCOsT3o-KMIVvMR6uSIicEL89XHvUu29d3Qhtb-o6fIL3nOXiU</recordid><startdate>202204</startdate><enddate>202204</enddate><creator>Nakanishi, Masaki</creator><creator>Khadiev, Kamil</creator><creator>Prusis, Krisjanis</creator><creator>Vihrovs, Jevgenijs</creator><creator>Yakaryılmaz, Abuzer</creator><general>World Scientific Publishing Company</general><general>World Scientific Publishing Co. Pte., Ltd</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>202204</creationdate><title>Exact Affine Counter Automata</title><author>Nakanishi, Masaki ; Khadiev, Kamil ; Prusis, Krisjanis ; Vihrovs, Jevgenijs ; Yakaryılmaz, Abuzer</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c262X-1d90aba7f685f94afbbf5b424e6785c8e76b6d786748acb23db7fe3a30f2dde83</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Languages</topic><topic>Polynomials</topic><topic>Real time</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Nakanishi, Masaki</creatorcontrib><creatorcontrib>Khadiev, Kamil</creatorcontrib><creatorcontrib>Prusis, Krisjanis</creatorcontrib><creatorcontrib>Vihrovs, Jevgenijs</creatorcontrib><creatorcontrib>Yakaryılmaz, Abuzer</creatorcontrib><collection>CrossRef</collection><jtitle>International journal of foundations of computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Nakanishi, Masaki</au><au>Khadiev, Kamil</au><au>Prusis, Krisjanis</au><au>Vihrovs, Jevgenijs</au><au>Yakaryılmaz, Abuzer</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Exact Affine Counter Automata</atitle><jtitle>International journal of foundations of computer science</jtitle><date>2022-04</date><risdate>2022</risdate><volume>33</volume><issue>3n04</issue><spage>349</spage><epage>370</epage><pages>349-370</pages><issn>0129-0541</issn><eissn>1793-6373</eissn><abstract>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.</abstract><cop>Singapore</cop><pub>World Scientific Publishing Company</pub><doi>10.1142/S012905412241009X</doi><tpages>22</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0129-0541
ispartof International journal of foundations of computer science, 2022-04, Vol.33 (3n04), p.349-370
issn 0129-0541
1793-6373
language eng
recordid cdi_proquest_journals_2666760153
source World Scientific Journals【Remote access available】
subjects Algorithms
Languages
Polynomials
Real time
title Exact Affine Counter Automata
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T20%3A53%3A26IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Exact%20Affine%20Counter%20Automata&rft.jtitle=International%20journal%20of%20foundations%20of%20computer%20science&rft.au=Nakanishi,%20Masaki&rft.date=2022-04&rft.volume=33&rft.issue=3n04&rft.spage=349&rft.epage=370&rft.pages=349-370&rft.issn=0129-0541&rft.eissn=1793-6373&rft_id=info:doi/10.1142/S012905412241009X&rft_dat=%3Cproquest_cross%3E2666760153%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c262X-1d90aba7f685f94afbbf5b424e6785c8e76b6d786748acb23db7fe3a30f2dde83%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2666760153&rft_id=info:pmid/&rfr_iscdi=true