Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages
type: Item
instance of: scholarly article
title: Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages
zbMATH Open document ID: 0603.68081
DOI: 10.1016/0304-3975(85)90164-1
author: Kathleen Ayers
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3974330
zbMATH Keywords: pushdown automaton
zbMATH Keywords: ordered grammar
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90164-1
OpenAlex ID: W2020370487
cites work: Grammars with partial ordering of the rules
cites work: Q4198075
cites work: Q5576254
cites work: Q5678435
cites work: Some restrictive devices for context-free grammars
description: scientific article; zbMATH DE number 3974330