A note on pushdown store automata and regular systems
HTML articles powered by AMS MathViewer
- by Sheila A. Greibach PDF
- Proc. Amer. Math. Soc. 18 (1967), 263-268 Request permission
References
- Y. Bar-Hillel, M. Perles, and E. Shamir, On formal properties of simple phrase structure grammars, Z. Phonetik Sprachwiss. Kommunikat. 14 (1961), 143–172. MR 151376
- J. Richard Büchi, Regular canonical systems, Arch. Math. Logik Grundlag. 6 (1964), 91–111 (1964). MR 169410, DOI 10.1007/BF01969548
- Noam Chomsky, On certain formal properties of grammars, Information and Control 2 (1959), 137–167. MR 105365 —, Context-free grammars and pushdown storage, Quarterly Progress Report No. 65, Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Mass., 1962.
- Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0124208 J. Evey, The theory and applications of pushdown store machines, Ph.D. Thesis, Harvard University, Cambridge, Mass., 1963.
- Seymour Ginsburg, The mathematical theory of context-free languages, McGraw-Hill Book Co., New York-London-Sydney, 1966. MR 0211815
- Seymour Ginsburg and Sheila A. Greibach, Deterministic context free languages, Information and Control 9 (1966), 620–648. MR 207486
- Seymour Ginsburg, Sheila A. Greibach, and Michael A. Harrison, Stack automata and compiling, J. Assoc. Comput. Mach. 14 (1967), 172–201. MR 239884, DOI 10.1145/321371.321385
- Seymour Ginsburg and G. F. Rose, Operations which preserve definability in languages, J. Assoc. Comput. Mach. 10 (1963), 175–195. MR 157515, DOI 10.1145/321160.321167
- Seymour Ginsburg and Edwin H. Spanier, Quotients of context-free languages, J. Assoc. Comput. Mach. 10 (1963), 487–492. MR 163808, DOI 10.1145/321186.321191
- S. C. Kleene, Representation of events in nerve nets and finite automata, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, N.J., 1956, pp. 3–41. MR 0077478 G. H. Matthews, A note on asymmetry in phrase structure grammars, Information and Control 7 (1964), 360-365.
- Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197–215. MR 7893, DOI 10.2307/2371809
- Emil L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11. MR 20527, DOI 10.2307/2267170
- M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114–125. MR 103795, DOI 10.1147/rd.32.0114 A. Thue, Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln, Skr. Vid.-Selskapet Kristiania. I, (1914), no. 10, 1-34.
Additional Information
- © Copyright 1967 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 18 (1967), 263-268
- MSC: Primary 94.40
- DOI: https://doi.org/10.1090/S0002-9939-1967-0209086-1
- MathSciNet review: 0209086