×

A note on pushdown store automata and regular systems. (English) Zbl 0183.01703


PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Y. Bar-Hillel, M. Perles, and E. Shamir, On formal properties of simple phrase structure grammars, Z. Phonetik Sprachwiss. Kommunikat. 14 (1961), 143 – 172. · Zbl 0106.34501
[2] J. Richard Büchi, Regular canonical systems, Arch. Math. Logik Grundlagenforsch. 6 (1964), 91 – 111 (1964). · Zbl 0129.26102
[3] Noam Chomsky, On certain formal properties of grammars, Information and Control 2 (1959), 137 – 167. · Zbl 0088.10801
[4] -, Context-free grammars and pushdown storage, Quarterly Progress Report No. 65, Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Mass., 1962.
[5] Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. · Zbl 0080.00902
[6] J. Evey, The theory and applications of pushdown store machines, Ph.D. Thesis, Harvard University, Cambridge, Mass., 1963. · Zbl 0196.52501
[7] Seymour Ginsburg, The mathematical theory of context-free languages, McGraw-Hill Book Co., New York-London-Sydney, 1966. · Zbl 0195.02301
[8] Seymour Ginsburg and Sheila A. Greibach, Deterministic context free languages, Information and Control 9 (1966), 620 – 648. · Zbl 0145.00802
[9] Seymour Ginsburg, Sheila A. Greibach, and Michael A. Harrison, Stack automata and compiling, J. Assoc. Comput. Mach. 14 (1967), 172 – 201. · Zbl 0153.01101
[10] Seymour Ginsburg and G. F. Rose, Operations which preserve definability in languages, J. Assoc. Comput. Mach. 10 (1963), 175 – 195. · Zbl 0192.07201
[11] Seymour Ginsburg and Edwin H. Spanier, Quotients of context-free languages, J. Assoc. Comput. Mach. 10 (1963), 487 – 492. · Zbl 0148.00803
[12] 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.
[13] G. H. Matthews, A note on asymmetry in phrase structure grammars, Information and Control 7 (1964), 360-365. · Zbl 0134.24603
[14] Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197 – 215. · Zbl 0063.06327
[15] Emil L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1 – 11. · Zbl 1263.03030
[16] M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114 – 125. · Zbl 0158.25404
[17] A. Thue, Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln, Skr. Vid.-Selskapet Kristiania. I, (1914), no. 10, 1-34. · JFM 45.0333.19
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.