General Problems of Formal Grammars

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

General Problems of Formal Grammars

Full text

Pdf (1.18 MB)

Source

Journal of the ACM (JACM) archive
Volume 17 , Issue 1 (January 1970) table of contents

Pages: 31 - 43

Year of Publication: 1970

ISSN:0004-5411

Author

Dennis F. Cudia

University of Wisconsin, Computer Science Department, Madison, Wisconsin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 19, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321556.321560 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BAR-HILLEL, Y., PERLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Z. Phonetik. Sprach. Kommunikations. 14 (1961), 143-172.
	2	BOONE, W.W. Word problems and recursively enumerable degrees of unsolvability: A first paper on Thue systems. Ann. Math. 83 (1966), 520-571.
	3	--. A sequel on finitely presented groups. Ann. Math. 84 (1966), 49-84.
	4	---. HAKEN, W., AND PO~NARU, V. On recursively unsolvable problems in topology and their classification. In Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam. (in press)
	5	David G. Cantor, On The Ambiguity Problem of Backus Systems, Journal of the ACM (JACM), v.9 n.4, p.477-479, Oct. 1962 [doi>10.1145/321138.321145]
	6	CHOMSKY, N. Formal properties of grammars. In Handbook of Mathematical Psychology, Vol. 2, R. D. Luce, R. R. Bush, and E. Galanter (Eds.), Wiley, New York, pp. 323-418.
	7	, AND SCHUTZENBERGER, M. P. The algebraic theory of context-free languages. In Computer Programming and Formal Systems, Braffort and Hirschberg (Eds.), North-Holland, Amsterdam, 1963, pp. 118-161.
	8	CUDIA, D .F . Equivalence of some unsolvable problems used in formal grammars. Notices Amer. Math. Soc. 14 (1967), 81-82.
	9	Dennis F. Cudia , Wilson E. Singletary, Degrees of Unsolvability in Formal Grammars, Journal of the ACM (JACM), v.15 n.4, p.680-692, Oct. 1968 [doi>10.1145/321479.321490]
	10	----, AND --. The Post correspondence problem. J. Symbol. Logic 83 (1968), 418-430.
	11	l)Avis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
	12	Robert W. Floyd, On ambiguity in phrase structure languages, Communications of the ACM, v.5 n.10, p.526, Oct. 1962 [doi>10.1145/368959.368993]
	13	Robert W. Floyd, Bounded context syntactic analysis, Communications of the ACM, v.7 n.2, p.62-67, Feb. 1964 [doi>10.1145/363921.363927]
	14	Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
	15	Seymour Ginsburg , Joseph Ullian, Ambiguity in context free languages, Journal of the ACM (JACM), v.13 n.1, p.62-89, Jan. 1966 [doi>10.1145/321312.321318]
	16	HARTMANIS, J., AND HOPCROFT, Z. E. Structure of undecidable problems in automata theory. Ninth Annual IEEE Syrup. on Switching and Automata Theory, 1968, pp. 327- 333.
	17	IHRIG, A. H. The Post-Linial theorems for arbitrary recursively enumerable degrees of unsolvability. Notre Dame J. Logic 6 (1965), 54-72.
	18	E. T. Irons, “Structural connections” in formal languages, Communications of the ACM, v.7 n.2, p.67-72, Feb. 1964 [doi>10.1145/363921.363931]
	19	KLEENE, S.C. Introduction to Metamathemalics. D. Van Nostrand, New York, 1952.
	20	-- Representation of events in nerve nets and finite automata. In Automata Studies, Princeton U. Press, Princeton, N.J., 1956, pp. 3-41.
	21	KNUTH, D .E . On the translation of languages from left to right. Inform. Contr. 8 (1965), 607-639.
	22	POST, E.L. Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc. 50 (1944), 284-316.
	23	-- A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946), 264-268.
	24	--. Recursive unsolvability of a problem of Thue. J. Symbol. Logic 11 (1947), 1-11.
	25	RABIN, M. O., AND SCOTT, D. Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114-125.
	26	SREPHERDSON, J. C. Machine configuration and word problems of given degree of unsolvability. Z. math. Logik u. Grundlageu d. Math. 11 (1965), 149-175.
	27	SINGLETARYY, W. E. The equivalence of some general combinatorial decision problems. Bull. Amer. Math. Soc. 73 (1967), 446-451.
	28	.... . Recursive unsolvability of a complex of problems proposed by Post. J. Fae. Sci., U. Tokyo 14 (1967), 25-58.
	29	Ann Yasuhara, A Remark on Post Normal Systems, Journal of the ACM (JACM), v.14 n.1, p.167-171, Jan. 1967 [doi>10.1145/321371.321384]

CITED BY 2

	Dennis F. Cudia, The degree hierarchy of undecidable problems of formal grammars, Proceedings of the second annual ACM symposium on Theory of computing, p.10-21, May 04-06, 1970, Northampton, Massachusetts, United States
	Dennis F. Cudia, The degree diagram of undecidable problems of formal grammars, ACM SIGACT News