
Accession Number : AD0713695
Title : A NOTE ON GRAMMARS WITH COORDINATES.
Descriptive Note : Technical rept.,
Corporate Author : MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER
Personal Author(s) : Milgram,David L. ; Rosenfeld,Azriel
Report Date : SEP 1970
Pagination or Media Count : 14
Abstract : Anderson has defined the notion of a 'graphical rewriting grammar', in which each production has an associated set of functions that compute coordinates for the symbols in the production's right member in terms of given coordinates of the symbols in its left member. It is shown that any such 'Anderson grammar' (AG) is equivalent to a 'onedimensional' AG whose productions are all 'leftlinear'; thus the power of an AG can be restricted only by restricting its coordinatecomputing functions. On the other hand, even if the productions of an AG are leftlinear and its functions are all computable by finite automata, its language need not be finitestate or even contextfree. (Author)
Descriptors : (*GRAMMARS, SET THEORY), ANALYSIS
Subject Categories : Linguistics
Distribution Statement : APPROVED FOR PUBLIC RELEASE