Linear iterated pushdowns

Weir, David (1994) Linear iterated pushdowns. Computational Intelligence, 10 (4). pp. 431-439. ISSN 0824-7935

Download (161kB) | Preview


This paper discusses variants of nondeterministic one-way S-automata and context-free S-grammars where S is a storage type. The framework that these systems provide can be used to give alternative formulations of embedded pushdown automata and linear indexed grammars. The embedded pushdown automata is obtained by means of a linear version of a class of storage types called iterated pushdowns. Linear indexed grammar is obtained by using the pushdown storage type and restricting the way in which the grammar uses its storage.

Item Type: Article
Additional Information: Published by Wiley-Blackwell
Keywords: grammar formalisms; string automata; mathematical linguistics; formal language theory
Schools and Departments: School of Engineering and Informatics > Informatics
Subjects: Q Science > QA Mathematics > QA0075 Electronic computers. Computer science
Depositing User: David Weir
Date Deposited: 21 Nov 2006
Last Modified: 07 Mar 2017 06:39
Google Scholar:17 Citations

View download statistics for this item

📧 Request an update