| One-way stack automata |
| Full text |
 Pdf
(1.59 MB)
|
| Source
|
Journal of the ACM (JACM)
archive
Volume 14 , Issue 2 (April 1967)
table of contents
Pages: 389 - 418
Year of Publication: 1967
ISSN:0004-5411
|
|
Authors
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 5, Downloads (12 Months): 44, Citation Count: 29
|
|
|
 ABSTRACT
A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation, the latter. Several solvability questions are also considered.
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., PERLE, M., AND SItAMIR, E. On formal properties of simple phrase structure grunm.-ars. Z. Phonelik, Sprachwissen. Kommunikationsforsch. 14 (1961), 143-172; in Y. Bar-Hillel, Language and Information, Addison-Wesley, Rending, Mass., 1965, pp. 116- 150.
|
| |
2
|
CHOMSKY, i . Oil certain formal properties of grammars. Inform. and Contr. (1959), 137-167.
|
| |
3
|
DAvis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
|
| |
4
|
GINSRURO, S., AND GREIBACH, S. Deterministic context free langaages. Inform. and Contr. 9 (1966), 62648.
|
 |
5
|
|
| |
6
|
RABIN, M., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959), 114-125.
|
CITED BY 29
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Detlef Wotschke, Degree-languages, polynomial time recognition, and the LBA problem, Proceedings of seventh annual ACM symposium on Theory of computing, p.145-152, May 05-07, 1975, Albuquerque, New Mexico, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
E.1