Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 21 / Issue 12

available in:   PDF (147 kB) PS (269 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-021-12-1563


Deterministic Frequency Pushdown Automata

Cristian S. Calude (The University of Auckland, New Zealand)

Rūsiņš Freivalds (University of Latvia, Latvia)

Sanjay Jain (National University of Singapore, Singapore)

Frank Stephan (National University of Singapore, Singapore)

Abstract: 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 mn/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 mn/2, L can be recognised by an (m, n)-DPDA but, for all m, n with 1 ≤ mn, L cannot be recognised by (m, n)-DFA.

Keywords: context-free sets, deterministic pushdown automata, frequency computation, regular sets

Categories: F.1.1, F.1.2