Abstract:
Frequency computation was introduced by Rose [26]. Trakhtenbrot [27] proved the existence of a continuum of functions computable
by frequency Turing machines with frequency 1/2 . In contrast, every function computable by a frequency Turing machine with frequency exceeding
1/2 is recursive. Essentially similar results for finite automata and other
types of machines have been proved by Kinber [19] and Austinat, Diekert,
Hertrampf, Petersen [4].
In this paper we introduce the notion of frequency pushdown automaton.
Answering a question E. Shamir posed at LATA 2013, we prove
that there is a language which is 1/1 -recognizable but which is not 2/n -
recognizable (for any n) by deterministic frequency pushdown automaton.
