CaltechAUTHORS
  A Caltech Library Service

Programming Language for Automata

Knuth, Donald E. and Bigelow, Richard H. (1967) Programming Language for Automata. Journal of the ACM, 14 (4). pp. 615-635. ISSN 0004-5411. http://resolver.caltech.edu/CaltechAUTHORS:20161117-130320052

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20161117-130320052

Abstract

The techniques of automatic programming are useful for constructive proofs in automata theory. A formal definition of an elementary programming language for a stack automaton is given, and it is shown how this may be readily adapted to other classes of automata. The second part of this paper shows how this programming language can be applied to automata theory, as we prove there are non-context-sensitive languages accepted by a stack automaton.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/321420.321421DOIArticle
http://dl.acm.org/citation.cfm?doid=321420.321421PublisherArticle
Additional Information:© 1967 ACM. Received February, 1967. The research reported in this paper was supported in part by the National Science Foundation and the Carnegie Corporation.
Funders:
Funding AgencyGrant Number
NSFUNSPECIFIED
Carnegie CorporationUNSPECIFIED
Record Number:CaltechAUTHORS:20161117-130320052
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20161117-130320052
Official Citation:Donald E. Knuth and Richard H. Bigelow. 1967. Programming Language for Automata. J. ACM 14, 4 (October 1967), 615-635. DOI=http://dx.doi.org/10.1145/321420.321421
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72126
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:17 Nov 2016 21:25
Last Modified:17 Nov 2016 21:25

Repository Staff Only: item control page