One-way nondeterministic real-time list-storage languages

ABSTRACT

A device is presented which has its memory organized as a linear list, a type of storage equivalent to having two pushdown stores. Attention is then focused on the nondeterministic automaton (called an lsa) which results when the input is read one-way and the device operates in real-time. The set of words (called a language) accepted by an lsa is extensively studied. In particular, several characterizations and closure properties of languages are given.

REFERENCES

• 1: Chomsky N. On certain formal properties of grammars. Inform. Contr. 2 (1959), 37-167.
• 2: DAVIS, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
• 3: Jerome A. Feldman, A formal semantics for computer languages and its application in a compiler-compiler, Communications of the ACM, v.9 n.1, p.3-9, Jan. 1966 [doi>10.1145/365153.365156]
• 4: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 5: -- AND GREIBACH, S. Abstract families of languages. SDC document TM-738/031/00.
• 6: Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, Stack automata and compiling, Journal of the ACM (JACM), v.14 n.1, p.172-201, Jan. 1967 [doi>10.1145/321371.321385]
• 7: Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, One-way stack automata, Journal of the ACM (JACM), v.14 n.2, p.389-418, April 1967 [doi>10.1145/321386.321403]
• 8: Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965 [doi>10.1145/321250.321254]
• 9: HAINES, L. H. Generation and recognition of formal languages. Ph.D. dissertation, M.I.T., Cambridge, Mass., June 1965.
• 10: HARTMANIS, J., AND STEARNS, R .E . On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285-306.
• 11: KUROnA, S. Y. Classes of languages and linear bounded automata. Inform. Contr. 7 (1964), 202-223.
• 12: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 13: OETTINGER, A. G. Automatic syntactic analysis and the pushdown store. In Structure of Language and Its Mathematical Aspects, Proc. Symposia in Applied Mathematics, Vol. 12, Amer. Math. Soc., Providence, R. I., 1961, pp. 104--129.
• 14: POST, E.L. Formal reductions of the general combinatOrial decision problem. Amer. J. Math. 6 (1943), 197-215.
• 15: RABIN, M.O. Real-time computation. Israel J. Math. 1 (1963), 203-211.
• 16: ---- AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959), 114-125.
• 17: Arnold L. Rosenberg, Real-Time Definable Languages, Journal of the ACM (JACM), v.14 n.4, p.645-662, Oct. 1967 [doi>10.1145/321420.321423]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Languages, Performance, Theory, Verification