<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//TaxonX//DTD Taxonomic Treatment Publishing DTD v0 20100105//EN" "../../nlm/tax-treatment-NS0.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:tp="http://www.plazi.org/taxpub" article-type="research-article" dtd-version="3.0" xml:lang="en">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">109</journal-id>
      <journal-id journal-id-type="index">urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891</journal-id>
      <journal-title-group>
        <journal-title xml:lang="en">JUCS - Journal of Universal Computer Science</journal-title>
        <abbrev-journal-title xml:lang="en">jucs</abbrev-journal-title>
      </journal-title-group>
      <issn pub-type="ppub">0948-695X</issn>
      <issn pub-type="epub">0948-6968</issn>
      <publisher>
        <publisher-name>Journal of Universal Computer Science</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.3217/jucs-021-12-1563</article-id>
      <article-id pub-id-type="publisher-id">23750</article-id>
      <article-categories>
        <subj-group subj-group-type="heading">
          <subject>Research Article</subject>
        </subj-group>
        <subj-group subj-group-type="scientific_subject">
          <subject>F.1.1 - Models of Computation</subject>
          <subject>F.1.2 - Modes of Computation</subject>
        </subj-group>
      </article-categories>
      <title-group>
        <article-title>Deterministic Frequency Pushdown Automata</article-title>
      </title-group>
      <contrib-group content-type="authors">
        <contrib contrib-type="author" corresp="yes">
          <name name-style="western">
            <surname>Calude</surname>
            <given-names>Cristian S. S.</given-names>
          </name>
          <email xlink:type="simple">cristian@cs.auckland.ac.nz</email>
          <uri content-type="orcid">https://orcid.org/0000-0002-8711-6799</uri>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Freivalds</surname>
            <given-names>Rūsiņš</given-names>
          </name>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Jain</surname>
            <given-names>Sanjay</given-names>
          </name>
          <xref ref-type="aff" rid="A2">2</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Stephan</surname>
            <given-names>Frank</given-names>
          </name>
          <xref ref-type="aff" rid="A2">2</xref>
        </contrib>
      </contrib-group>
      <aff id="A1">
        <label>1</label>
        <addr-line content-type="verbatim">University of Latvia, Riga, Latvia</addr-line>
        <institution>University of Latvia</institution>
        <addr-line content-type="city">Riga</addr-line>
        <country>Latvia</country>
      </aff>
      <aff id="A2">
        <label>2</label>
        <addr-line content-type="verbatim">National University of Singapore, Singapore, Singapore</addr-line>
        <institution>National University of Singapore</institution>
        <addr-line content-type="city">Singapore</addr-line>
        <country>Singapore</country>
      </aff>
      <author-notes>
        <fn fn-type="corresp">
          <p>Corresponding author: Cristian S. S. Calude (<email xlink:type="simple">cristian@cs.auckland.ac.nz</email>).</p>
        </fn>
        <fn fn-type="edited-by">
          <p>Academic editor: </p>
        </fn>
      </author-notes>
      <pub-date pub-type="collection">
        <year>2015</year>
      </pub-date>
      <pub-date pub-type="epub">
        <day>01</day>
        <month>12</month>
        <year>2015</year>
      </pub-date>
      <volume>21</volume>
      <issue>12</issue>
      <fpage>1563</fpage>
      <lpage>1576</lpage>
      <uri content-type="arpha" xlink:href="http://openbiodiv.net/5ACB2B29-D7C5-527E-AE77-EFA22EA0BB22">5ACB2B29-D7C5-527E-AE77-EFA22EA0BB22</uri>
      <uri content-type="zenodo_dep_id" xlink:href="https://zenodo.org/record/5505859">5505859</uri>
      <history>
        <date date-type="received">
          <day>22</day>
          <month>05</month>
          <year>2014</year>
        </date>
        <date date-type="accepted">
          <day>27</day>
          <month>01</month>
          <year>2015</year>
        </date>
      </history>
      <permissions>
        <copyright-statement>Cristian S. S. Calude, Rūsiņš Freivalds, Sanjay Jain, Frank Stephan</copyright-statement>
        <license license-type="creative-commons-attribution" xlink:href="" xlink:type="simple">
          <license-p>This article is freely available under the J.UCS Open Content License.</license-p>
        </license>
      </permissions>
      <abstract>
        <label>Abstract</label>
        <p>A set L is (m, n)-computable iff there is a mechanism which on input of n different words produces n conjectures whether these words are in L, respectively, such that at least m of these conjectures are right. Prior studies dealt with (m, n)- computable sets in the contexts of recursion theory, complexity theory and the theory of finite automata. The present work aims to do this with respect to computations by deterministic pushdown automata (using one common stack while processing all input words in parallel). We prove the existence of a deterministic context-free language L which is recognised by an (1, 1)-DPDA but fails to be recognised by any (m, n)-DPDA, where n ≥ 2 and m ≥ n/2+1. This answers a question posed by Eli Shamir at LATA 2013. Furthermore, it is shown that there is a language L such that, for all m, n with m ≤ n/2, L can be recognised by an (m, n)-DPDA but, for all m, n with 1 ≤ m ≤ n, L cannot be recognised by (m, n)-DFA.</p>
      </abstract>
    </article-meta>
  </front>
</article>
