Operations Which Preserve Definability in Languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Operations Which Preserve Definability in Languages

Full text

Pdf (1.22 MB)

Source

Journal of the ACM (JACM) archive
Volume 10 , Issue 2 (April 1963) table of contents

Pages: 175 - 195

Year of Publication: 1963

ISSN:0004-5411

Authors

Seymour Ginsburg	System Development Corporation, Santa Monica, California
G. F. Rose	System Development Corporation, Santa Monica, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 29, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/321160.321167 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	Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
	2	BAR-HillEl; PERLES; SHAMIR. On formal properties of imple phrase structure grammrs. Zeit. Phonelik, Sprachwiss. Konmunik. 14, (1961) 143-172.
	3	CHOMSKY, N. Finite state languages. Inform. Contr. 1, (1958) 91-112.
	4	CHOMSKY. N. On certain formal properties of grammars. Inform. Contr., (1959) 137- 167.
	5	ELGOT, C- Decision problems of finite automata design and related problems. Trans. Am. Math. Soc. 98, (1961) 2t-51.
	6	Seymour Ginsburg , H. Gordon Rice, Two Families of Languages Related to ALGOL, Journal of the ACM (JACM), v.9 n.3, p.350-371, July 1962 [doi>10.1145/321127.321132]
	7	RABIN Scovr. Finite automata and their decisioa problems. IBM J. Res. D- veloP. 2, (1959) 114 125.
	8	SCHINBnG, S. NoTE, oN he Boolean properie o context free languages. Inform. ConTr. S, (19f.) a72-75.

CITED BY 13

	Seymour Ginsburg , Thomas N. Hibbard, Solvability of Machine Mappings of Regular Sets to Regular Sets, Journal of the ACM (JACM), v.11 n.3, p.302-312, July 1964
	Seymour Ginsburg , Joseph Ullian, Preservation of unambiguity and inherent ambiguity in context-free languages, Journal of the ACM (JACM), v.13 n.3, p.364-368, July 1966
	Kojiro Kobayashi , Shigeru Sekiguchi, On the Class of Predicates Decidable by Two-Way Multitape Finite Automata, Journal of the ACM (JACM), v.13 n.2, p.236-261, April 1966
	Thomas N. Hibbard, Context-Limited Grammars, Journal of the ACM (JACM), v.21 n.3, p.446-453, July 1974
	Gene F. Rose, An extension of ALGOL-like languages, Communications of the ACM, v.7 n.2, p.52-61, Feb. 1964
	Sheila A. Greibach, The Unsolvability of the Recognition of Linear Context-Free Languages, Journal of the ACM (JACM), v.13 n.4, p.582-587, Oct. 1966
	Seymour Ginsburg , Edwin H. Spanier, Quotients of Context-Free Languages, Journal of the ACM (JACM), v.10 n.4, p.487-492, Oct. 1963
	Seymour Ginsburg , Edwin H. Spanier, Mappings of languages by two-tape devices, Journal of the ACM (JACM), v.12 n.3, p.423-434, July 1965
	Seymour Ginsburg , Joseph Ullian, Ambiguity in context free languages, Journal of the ACM (JACM), v.13 n.1, p.62-89, Jan. 1966
	R. James Evey, Application of pushdown-store machines, Proceedings of the November 12-14, 1963, fall joint computer conference, November 12-14, 1963, Las Vegas, Nevada
	R. J. Nelson, Invited papers—1: basic concepts of automata theory, Proceedings of the 1965 20th national conference, p.138-161, August 24-26, 1965, Cleveland, Ohio, United States
	Bruce W. Arden, The role of programming in a Ph.D. computer science program, Communications of the ACM, v.12 n.1, p.31-37, Jan. 1969
	Saul Gorn, Mechanical languages: a course specification, Communications of the ACM, v.7 n.4, p.219-222, April 1964