Premium
LINEAR ITERATED PUSHDOWNS
Author(s) -
Weir David J.
Publication year - 1994
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1994.tb00007.x
Subject(s) - embedded pushdown automaton , deterministic context free grammar , deterministic pushdown automaton , pushdown automaton , computer science , nondeterministic algorithm , iterated function , context free language , context free grammar , nested word , rule based machine translation , discrete mathematics , mathematics , algorithm , tree adjoining grammar , theoretical computer science , automaton , automata theory , nondeterministic finite automaton , artificial intelligence , quantum finite automata , mathematical analysis
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.