Linear iterated pushdowns

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

[img]
Preview
PDF
Download (161kB) | Preview

Abstract

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
Q Science > QA Mathematics > QA0076 Computer software
Depositing User: David Weir
Date Deposited: 21 Nov 2006
Last Modified: 07 Mar 2017 06:39
URI: http://sro.sussex.ac.uk/id/eprint/498
Google Scholar:17 Citations

View download statistics for this item

📧 Request an update