Two Families of Languages Related to ALGOL

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Two Families of Languages Related to ALGOL

Full text

Pdf (1.09 MB)

Source

Journal of the ACM (JACM) archive
Volume 9 , Issue 3 (July 1962) table of contents

Pages: 350 - 371

Year of Publication: 1962

ISSN:0004-5411

Authors

Seymour Ginsburg	System Development Corporation, Santa Monica, California
H. Gordon Rice	Computer Sciences Corp., Palos Verdes, Calif and System Development Corporation, Santa Monica, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 69, Citation Count: 40

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/321127.321132 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, PERLIS, and SHAMIR. On formal properties of simple phrase structure grammars. Tech. Rep. No. 4 (July 1960). Applied Logic Branch, The Hebrew University of Jerusalem.
	3	BUCHE, J. Regular canonical stems and finite automata. Department of Philosophy, Technical Report, December 1959, University of Michigan, Ann Arbor, Michigan.
	4	CHOMSKY, N. Three models for thc description of language. IRE Trans. Inf. Theory 2 (1956), 113-124.
	5	CHOMSKY, N Finite state lailguages. Infor'mation and Control 1 (1958), 91-112
	6	CHOMSKY, N. Oil certain formal properties of grammars. Information and Control (1959), 137-167.
	7	DAVIS, M. ComputabiIzty and UnsolvabiIity. McGraw Hill, New York (1958).
	8	RABIN and SCOTT Finite automata and their decision problcms IBM J. Res. Dev. 8 (1959), 114-125.
	9	SSCHEINBERG, S. N~)te on the Boolean properties of context free languages. Information and Control 3 (1960), 372-375.
	10	TARSKI, A. A lattice-theoretical fixpoint theorem and its applications. Pacific J. Matl~. 5 (1955), 285-309.

CITED BY 41

	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
	Armando B. Matos, An introduction to ultimately periodic sets of integers, ACM SIGACT News, v.25 n.1, p.90-96, March 1994
	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
	Philip Gilbert , William G. McLellan, Compiler generation using formal specification of procedure-oriented and machine languages, Proceedings of the April 18-20, 1967, spring joint computer conference, April 18-20, 1967, Atlantic City, New Jersey
	Gene F. Rose, An extension of ALGOL-like languages, Communications of the ACM, v.7 n.2, p.52-61, Feb. 1964
	Richard Johnsonbaugh , David P. Miller, Converses of pumping lemmas, ACM SIGCSE Bulletin, v.22 n.1, p.27-30, Feb. 1990
	Sven Skyum, On decomposing languages defined by parallel devices, Proceedings of seventh annual ACM symposium on Theory of computing, p.121-125, May 05-07, 1975, Albuquerque, New Mexico, United States
	Alexander Okhotin, The dual of concatenation, Theoretical Computer Science, v.345 n.2-3, p.425-447, 22 November 2005
	Alexander Okhotin, Unambiguous Boolean grammars, Information and Computation, v.206 n.9-10, p.1234-1247, September, 2008
	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 , Gene F. Rose, Some Recursively Unsolvable Problems in ALGOL-Like Languages, Journal of the ACM (JACM), v.10 n.1, p.29-47, Jan. 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
	Alexander Okhotin, Computational Universality in One-variable Language Equations, Fundamenta Informaticae, v.74 n.4, p.563-578, December 2006
	Seymour Ginsburg , G. F. Rose, Operations Which Preserve Definability in Languages, Journal of the ACM (JACM), v.10 n.2, p.175-195, April 1963
	Daniel J. Rosenkrantz, Matrix Equations and Normal Forms for Context-Free Grammars, Journal of the ACM (JACM), v.14 n.3, p.501-507, July 1967
	Alexander Okhotin , Oksana Yakimova, Language equations with complementation: Decision problems, Theoretical Computer Science, v.376 n.1-2, p.112-126, May, 2007
	Philip Gilbert, On the Syntax of Algorithmic Languages, Journal of the ACM (JACM), v.13 n.1, p.90-107, Jan. 1966
	Seymour Ginsburg , Joseph Ullian, Ambiguity in context free languages, Journal of the ACM (JACM), v.13 n.1, p.62-89, Jan. 1966
	Peter R. J. Asveld, Generating all permutations by context-free grammars in Chomsky normal form, Theoretical Computer Science, v.354 n.1, p.118-130, 21 March 2006
	M. Hennessy, Acceptance trees, Journal of the ACM (JACM), v.32 n.4, p.896-928, Oct. 1985
	Alexander Okhotin, Unresolved systems of language equations: expressive power and decision problems, Theoretical Computer Science, v.349 n.3, p.283-308, 16 December 2005
	Werner Kuich, Forty years of formal power series in automata theory, A half-century of automata theory: celebration and inspiration, World Scientific Publishing Co., Inc., River Edge, NJ, 2001
	Stefan Andrei , Salvador Valerio Cavadini , Wei-Ngan Chin, A new algorithm for regularizing one-letter context-free grammars, Theoretical Computer Science, v.306 n.1-3, p.113-122, 5 September 2003
	Peter R. J. Asveld, Generating all permutations by context-free grammars in Greibach normal form, Theoretical Computer Science, v.409 n.3, p.565-577, December, 2008
	Alexander Okhotin, Boolean grammars, Information and Computation, v.194 n.1, p.19-48, 10 October 2004
	Sheila A. Greibach, Some restrictions on W-grammars, Proceedings of the sixth annual ACM symposium on Theory of computing, p.256-265, April 30-May 02, 1974, Seattle, Washington, United States
	W. H. Burge, The evaluation, classification and interpretation of expressions, Proceedings of the 1964 19th ACM national conference, p.11.401-11.4022, January 1964
	Patrick Cousot , Radhia Cousot, Bi-inductive structural semantics, Information and Computation, v.207 n.2, p.258-283, February, 2009
	Andreas Klein , Martin Kutrib, Cellular Devices and Unary Languages, Fundamenta Informaticae, v.78 n.3, p.343-368, August 2007
	Zoltán Fülöp , Heiko Vogler, Weighted tree transducers, Journal of Automata, Languages and Combinatorics, v.9 n.1, p.31-54, January 2004
	James W. Thatcher, Transformations and translations from the point of view of generalized finite automata theory, Proceedings of the first annual ACM symposium on Theory of computing, p.129-142, May 05-07, 1969, Marina del Rey, California, United States
	Michael A. Arbib , Ernest G. Manes, The Pattern-of-Calls Expansion Is the Canonical Fixpoint for Recursive Definitions, Journal of the ACM (JACM), v.29 n.2, p.577-602, April 1982
	Symeon Bozapalidis, Context-free series on trees, Information and Computation, v.169 n.2, p.186-229, September 15, 2001
	Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965
	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
	F. L. Bauer, The Cellar Principle of State Transition and Storage Allocation, IEEE Annals of the History of Computing, v.12 n.1, p.41-49, January 1990
	Robert G. Trout, A compiler—compiler system, Proceedings of the 1967 22nd national conference, p.317-322, January 1967, Washington, D.C., United States
	T. V. Griffiths , S. R. Petrick, On the relative efficiencies of context-free grammar, Communications of the ACM, v.8 n.5, p.289-300, May 1965
	Davide Sangiorgi, On the origins of bisimulation and coinduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.31 n.4, p.1-41, May 2009
	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