QRT FIFO AUTOMATA, BREADTH-1ST GRAMMARS AND THEIR RELATIONS

Some classes of queue automata (deterministic and nondeterministic), i.e. machines equipped with one or more FIFO tapes, and corresponding languages are considered. For quasi-real-time (QRT) deterministic machines, recognition power, closure properties and counting capabilities are studied. For such machines, by showing that the language L(J) = [GRAPHICS] can be recognized with J queues but not with fewer, an infinite hierarchy theorem, which contradicts the known results for nondeterministic machines, is proved. Restricted palindromes can be recognized with two queues. We introduce a generative system for some queue languages, the breadth-first context-free grammars (BCF), which are the same as context-free grammars but for the ordering of terminals which is breadth-first, i.e. the least recently produced nonterminal symbol must be rewritten first. BCF languages are recognized essentially by stateless queue automata; they are semilinear, closed with respect to permutation and homomorphism, but not with respect to intersection with regular sets. A periodicity property (pumping lemma) is proved for BCF languages, whence comparisons with other families are obtained. Finally, a homomorphic characterization of any queue language is presented: L = h(R intersection-of B), where h is a homomorphism (nonerasing if L is QRT), R a regular set and B a BCF language. The result can be extended to multiqueue automata.