Frequency computation was introduced in [16]. Trakhtenbrot [17] proved the existence of a continuum of functions computable by frequency Turing machines with frequency 12 . In contrast, every function computable by a frequency Turing machine with frequency exceeding 12 is recursive. Essentially similar results for finite automata and other types of machines have been proved in [12] and [1]. We consider frequency pushdown automata. They are specific types of automata because allowing several pushdown stores would add too much computation power but allowing only one pushdown store restricts the computation power.
Answering a problem by Myhill (see McNaughton [
The notion of frequency computation has been extended to other models of
computation. Frequency computation in polynomial time was discussed in full
detail in [
When restricted to a one-letter alphabet, every (m; n)-recognizable language
is regular (cf. [
Frequency computations became increasingly popular when relations between
frequency computation and computation with a small number of queries was
discovered [
Let be any finite alphabet, and let be the free monoid generated by . The binary alphabet B is denoted by B. Every subset L is said to be a language. The elements of are called strings ; jxj denotes the length of a string x 2 . By L : ! f0; 1g we denote the characteristic function of L.
A deterministic pushdown automaton (PDA) is a 7-tuple M = (Q; ; ; ; q0; Z; F ) where Q is a finite set of states, is a finite set which is called the input alphabet, is a finite set which is called the stack alphabet, q0 2 Q is the start state, Z 2 is the initial stack symbol, and F Q is the set of accepting states. An element (p; a; A; q; ) 2 is a transition of M . It has the intended meaning that M , in state p 2 Q, with a 2 [ f"g on the input and with A 2 as topmost stack symbol, may read a, change the state to q, pop A, replacing it by pushing 2 . The ( [ f"g) component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.
For n-frequency pushdown automata we modify the above definition allowing
n input words. However, we need to be aware that for the general case input
words can be of distinct lengths. Our definition closely models the definition of
n-frequency finite automata (see, e.g. [
A deterministic n-frequency automaton (n-DFA) is a 7-tuple A = [Q; ; #; ; q0; ; n], where n 2 N, n 1, Q is a finite set of states, q0 is the initial state, is a finite alphabet and # is a symbol not in . The mapping : Q ( [ f#g)n ! Q is the transition function; the function : Q ! Bn is the type of state which is used for outputs. The type is interpreted as an n-tuple of answers i: its i-th component records whether the i-th input word read from the i-th input up to the current moment belongs to the language. We use the notation (q; (x1#`1 ; : : : ; xn#`n )) to denote the type after reading the inputs the words (x1#`1 ; : : : ; xn#`n ).
Next we formally describe the behavior of an n-DFA A. Let n 2 N+, and let x = (x1; : : : ; xn) 2 ( )n be an input vector. We define jxj = maxfjxij j 1 i ng, and q x = (q; (x1#`1 ; : : : ; xn#`n )), where : Q (( [ f#g)n) is the usual extension of on n-tuples of strings, and `i = jxj jxij for all 1 i n. The output of A is defined to be the type (q0 x).
A language L is said to be (m; n)-recognized by an n-DFA A if for each n-tuple (x1; : : : ; xn) 2 ( )n of pairwise distinct strings the tuples (q0 x) and ( L(x1); : : : ; L(xn)) coincide on at least m components. A language L is called (m; n)-recognizable if there is an n-DFA A that (m; n)-recognizes L.
To define deterministic n-frequency pushdown automata (with only one pushdown store) the transition function will be extended for n-tuples : Q n ( [ f"g) ! Q ( [ f"g).
A deterministic n-frequency pushdown automaton (n-DFPA) is a 9-tuple A = (Q; ; #; ; ; q0; ; Z; F ), where # 62 and (Q; [ f#g; ; ; q0; ; Z; F ) is a PDA.
Let n 2 N+, and let x = (x1; : : : ; xn) 2 ( )n be an n-tuple. We define jxj = maxfjxij j 1 i ng, and q x =
(q; (x1#`1 ; : : : ; xn#`n )); where `i = jxj jxij for all 1 i n. Then the output of A is defined to be the type (q0 x). We emphasize that the n-DFPA contains only one pushdown tape which is used to process all n inputs.
A language L is said to be (m; n)-recognized by an n-DFPA A if for each n-tuple (x1; : : : ; xn) 2 ( )n of pairwise distinct strings the tuples (q0 x) and ( L(x1); : : : ; L(xn)) coincide on at least m components. A language L is called (m; n)-recognizable if there is an n-DFPA A that (m; n)-recognizes L. 3
A: By N = f0; 1; 2; : : : g we denote the set of nonnegative integers and B = f0; 1g. [n] = f1; 2; : : : ; ng. We use jXj to denote the cardinality of a set X.
Let A N be a set. By cA : N ! B we denote the characteristic function of cA (x) = (1; if x 2 A
0; if x 2= A We say that a function is recursive if there is an algorithm (Turing machine) that computes the function. If cA is a total recursive function then we call the set A recursive. Definition 1. A set A is (m; n)–computable iff there is a total recursive function f which assigns to all distinct inputs x1; x2; : : : ; xn a binary vector (y1; y2; : : : ; yn) such that at least m of the equations cA (x1) = y1; cA (x2) = y2; : : : ; cA (xn) = yn hold.
By a structure of a finite set K we call a set of K’s subsets S 2K .
We assume that the elements of K are ordered under some fixed ordering : K ! [n] where n = jKj.
Definition 2. A set A is (S; K)–computable (or computable with a structure S) iff there is a total recursive function f which assigns to all distinct inputs x1; x2; : : : ; xn a binary vector (y1; y2; : : : ; yn) such that 9B 2 S 8b 2 B A x (b) = y (b).
It can be seen that (m; n)–computing is a special case of (S; K)–computing by taking S to be the set of all subsets of K of size m. 4
In finite geometry, the Fano plane (named after Gino Fano) is the finite projective plane of order 2, having the smallest possible number of points and lines. This plane has 7 points and 7 lines with 3 points on every line and 3 lines through every point. Every two points are on a unique line and every two lines intersect in a unique point.
We consider the first example of what we call structured frequency algorithm. Definition 3. A set A is Fano-computable iff there exists a recursive operator R : N 7 ! f0; 1g7 such that, for all 7-tuples (x0; x1; ; x6) 2 N 7 of mutually distinct natural numbers, [(R(x0) = cA(x0) ^ R(x1) = cA(x1) ^ R(x3) = cA(x3))_ _(R(x1) = cA(x1) ^ R(x2) = cA(x2) ^ R(x4) = cA(x4))_ _(R(x2) = cA(x2) ^ R(x3) = cA(x3) ^ R(x5) = cA(x5))_ _(R(x3) = cA(x3) ^ R(x4) = cA(x4) ^ R(x6) = cA(x6))_ (R(x4) = cA(x4) ^ R(x5) = cA(x5) ^ R(x0) = cA(x0))_ _(R(x5) = cA(x5) ^ R(x6) = cA(x6) ^ R(x1) = cA(x1))_ _(R(x6) = cA(x6) ^ R(x0) = cA(x0) ^ R(x2) = cA(x2))] where R(xi) denotes the i-th component of R(x0; x1; ; x6).
Theorem 1. (K.Balodis,J.Iraids, R.Freivalds [
Now consider the language M = fw2wrev j w 2 B g which is clearly (1; 1)recognizable by a 2-DFPA.
Theorem 2. (C.Calude, R.Freivalds, F.Stephan [
Theorem 2 can be strengthened as follows: Theorem 3. The language M = fw2wrev j w 2 B g is (1; 1)-recognizable but for all n it is not (n; n)-recognizable by a 2-DFPA.
Theorem 4. If a set A is Fano-computable by a 7–DFPA, then it is computable by a 1–DFPA.