
Accession Number : AD0660886
Title : NEW PROOFS OF OLD THEOREMS IN LOGIC AND FORMAL LINGUISTICS,
Corporate Author : CARNEGIE INST OF TECH PITTSBURGH PA
Personal Author(s) : Floyd,Robert W.
Report Date : NOV 1966
Pagination or Media Count : 19
Abstract : Theorem 1 constructs, from any word problem in a semiThue system, an equivalent Post correspondence problem, showing the undecidability of the general Post correspondence problem. Theorem 2 constructs, from any Post correspondence problem, a minimal linear grammar which is ambiguous exactly if the Post correspondence problem has a solution, showing the undecidability of the general ambiguity problem. (Other standard undecidability results on phrase structure grammars are implied.) Theorem 3 constructs, from any word problem in a semiThue system, an ambiguity problem, combining the results of Theorem 1 and 2 by more direct means. No new results are presented, but standard proofs were shortened and constructions eliminated, combined, or simplified. (Author)
Descriptors : (*LINGUISTICS, THEOREMS), GRAMMARS
Subject Categories : Linguistics
Distribution Statement : APPROVED FOR PUBLIC RELEASE