article

Free access

Automata, formal languages abstract switching, and computability in a Ph.D. computer science program

Author:

Robert McNaughtonAuthors Info & Claims

Communications of the ACM, Volume 11, Issue 11

Pages 738 - 740

https://doi.org/10.1145/364139.364150

Published: 01 November 1968 Publication History

Abstract

A number of courses are listed in the area described as automata, formal languages, abstract switching, and computability, that might be available to a Ph.D. student in computer science. A brief catalog description of each course is supplied and the role of each of the courses in the graduate program is discussed.

References

[1]

ARBIB, M. Brains, Machines and Mathematics. McGraw-Hill, New York, 1964.

Digital Library

[2]

CALDWELL, S. Switching Circuits and Logical Design. Wiley, New York, 1958.

[3]

CHOMSKY, N. Aspects of Linguistics. M.I.T. Press, Cambridge, Mass., 1966.

[4]

DAVIS, MARTIN. Computability and Unsolvability. McGraw- Hill, New York, 1958.

[5]

- (Ed.). The Undecidable: Basic Papers on Undecidable Problems and Computable Functions. Raven, Hewlett, N.Y., 1965.

Digital Library

[6]

GILL, A. Introduction to the Theory of Finite-State Machines. McGraw-Hill, New York, 1962.

[7]

GINSBURG, S. An Introduction to Mathematical Machine Theory. Addison-Wesley, Reading, Mass., 1962.

Digital Library

[8]

--. The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York, 1966.

Digital Library

[9]

GLUSHKOV, VIKTOR M. Introduction to Cybernetics. (Trans.). Academic Press, New York, 1966.

[10]

HARRISON, M. Introduction to Switching and Automata Theory. McGraw-Hill, New York, 1965.

[11]

HARTMANIS, J., AND STEARNS, R. E. Algebraic Structure of Sequential Machines. Prentice-Hall, Englewood Cliffs, N.J., 1966.

Digital Library

[12]

HENNIE, FREDERICK C. Finite-State Models for Logical Machines. Wiley, New York, 1968.

[13]

HERMES, H. Enumerability, Decidability and Computability: An Introduction to the Theory of Recursive Functions (trans.). Academic Press, New York, 1965.

[14]

HUMPHREY, W. S. Switching Circuits with Computer Applications. McGraw-Hill, New York, 1958.

[15]

KNUTH, DONALD E. The Art of Computer Programming, Vol. 9, Theory of Languages. Addison-Wesley, Reading, Mass. ( in press).

Digital Library

[16]

KOBRINSKII, N. E., AND TRAKHTENBROT, B. A. Introduction to the Theory of Finite Automata (trans.). North-Holland, Amsterdam, 1965.

[17]

KORFHAGE, R. Logic and Algorithms. Wiley, New York, 1966.

[18]

McCLUSKEY, E. J. Introduction to the Theory of Switching Circuits. McGraw-Hill, New York, 1965.

[19]

MILLER, RAYMOND E. Switching Theory, Vol. 1. Wiley, New York, 1965.

[20]

MINSKY, M. Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, N.J., 1967.

Digital Library

[21]

MOORE, E. F. (Ed.). Sequential Machines: Selected Papers. Addison-Wesley, Reading, Mass., 1964.

Digital Library

[22]

NELSON, R. J. Introduction to Automata. Wiley, New York, 1967.

[23]

PETER, R. Rekursive Funktionen. Akademiai Kinds, Budapest, 1951.

[24]

PHISTER, M. Logical Design of Digital Computers. Wiley, New York, 1958.

[25]

ROGERS, H. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.

Digital Library

[26]

SHANNON, C. E., AND McCARTHY, J. (Eds.). Automata Studies. Princeton U. Press, Princeton, N.J., 1956.

[27]

TRAKHTENBROT, B. A. Algorithms and Automatic Computing Machines (Trans.). Heath, Boston, Mass., 1963.

Cited By

Austing RBarnes BEngel G(1977)A survey of the literature in computer science education since curriculum '68Communications of the ACM10.1145/359367.35941720:1(13-21)Online publication date: 1-Jan-1977
https://dl.acm.org/doi/10.1145/359367.359417
Fosdick L(1974)Computer Science Programs at Universities Awarding the Ph.D. DegreeProceedings of the twelfth annual SIGCPR conference10.1145/800151.804887(40-47)Online publication date: 18-Jul-1974
https://dl.acm.org/doi/10.1145/800151.804887

Recommendations

Limited Automata and Context-Free Languages
Non-Classical Models of Automata and Applications V

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence ...
5′ → 3′ Watson-Crick Automata With Several Runs
Non-Classical Models of Automata and Applications

5′ → 3′ WK-automata are Watson-Crick automata whose two heads start on opposite ends of the input word and always run in opposite directions. One full reading in both directions is called a run. We prove that the expressive power of these automata ...
Left-most derivation and shadow-pushdown automata for context-sensitive languages
ICCOMP'06: Proceedings of the 10th WSEAS international conference on Computers

In this paper left-most derivation for context-sensitive grammars is presented based on Penttonen one-sided normal-form. The derivations using grammars in normal form are represented by tree-like graphs. Left-most derivation is defined in the sense of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 11, Issue 11

Nov. 68

84 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/364139

Editor:
Gerard Salton
Cornell Univ., Ithaca, NY

Issue’s Table of Contents

Copyright © 1968 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1968

Published in CACM Volume 11, Issue 11

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
614
Total Downloads

Downloads (Last 12 months)82
Downloads (Last 6 weeks)14

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Austing RBarnes BEngel G(1977)A survey of the literature in computer science education since curriculum '68Communications of the ACM10.1145/359367.35941720:1(13-21)Online publication date: 1-Jan-1977
https://dl.acm.org/doi/10.1145/359367.359417
Fosdick L(1974)Computer Science Programs at Universities Awarding the Ph.D. DegreeProceedings of the twelfth annual SIGCPR conference10.1145/800151.804887(40-47)Online publication date: 18-Jul-1974
https://dl.acm.org/doi/10.1145/800151.804887

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents