Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages (Q1082824)

The purpose of this paper is to define \(\lambda\)-linearly bounded deque automata and to establish some of the properties of the family of languages \({\mathcal D}\) accepted by the \(\lambda\)-linearly bounded deque automata. A deque automaton is basically a pushdown automaton which is capable of putting symbols on both the top and the bottom of the stack. We will first show that \({\mathcal L}_ 2\varsubsetneq {\mathcal D}\subseteq {\mathcal L}_ 1\). Then we will exhibit an ordered grammar associated with a deque automaton. Next we show that, given a deque language L, it is decidable whether or not \(L=\emptyset\). Then the closure properties of \({\mathcal D}\) will be discussed and finally we will establish the fact that \({\mathcal D}\) contains all of the semilinear bounded languages.