Abstract
A stack-counter acceptor is a stack acceptor in which the storage alphabet is just one letter. The present paper discusses multi-stack-counter acceptors operating in quasirealtime, i.e., acceptors in which each storage tape is a stack counter and in which there are only a bounded number of consecutive∈-moves. For each positive integerk let
be the family of languages accepted byk-stack-counter acceptors (k-counter acceptors). Each
is a principal AFL closed under reversal but not under∈-free substitution or under intersection. Also,
and a specific language in each
, is exhibited. For each
and there are noi andj such that
. It is shown that a quasi-real-timek-stackcounter acceptor is equivalent to one operating in non-deterministic real time. Lastly, it is shown that acceptance by final state of ak-stack-counter acceptor is equivalent to acceptance by empty tape and final state.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Book andS. Greibach, Quasi-realtime languages,Math. Systems Theory 4 (1970), 97–111.
P. Fischer, Turing machines with restricted memory aecess,Information and Control 9 (1966), 364–379.
P. Fischer, A. Meyer andA. Rosenberg, Counter machines and counter languages,Math. Systems Theory 2 (1968), 265–283.
S. Ginsburg andS. Greibach, Abstract families of languages, inStudies in Abstraet Families of Languages, Memoirs Amer. Math. Soc. No. 87, pp. 1–32, 1969.
S. Ginsburg andS. Greibach, Principal AFL,J. Computer System Sciences 4 (1970), 308–338.
S. Ginsburg, S. Greibach andM. Harrison, One-way stack automata,J. Assoc. Comput. Mach. 14 (1967), 389–418.
S. Ginsburg, S. Greibach andJ. Hopcroft, Pre-AFL, inStudies in Abstract Families of Languages, Memoirs Amer. Math. Soc. No. 87, pp. 41–51, 1969.
S. Ginsburg andM. Harrison, On the closure of AFL under reversal,Information and Control 17 (1970), 395–409.
S. Ginsburg andG. F. Rose, The equivalence of stack-counter aceeptors and quasirealtime stack-counter acceptors, to appear.
S. Greibach andS. Ginsburg, Multitape AFA,J. Assoc. Comput. Mach., to appear.
S. Greibach andJ. Hopcroft, Scattered context grammars,J. Computer System Sciences 3 (1969) 233–247.
J. Hartmanis andR. Stearns, On the computational eomplexity of algorithms,Trans. Amer. Math. Soc. 117 (1965), 285–306.
M. Minsky, Recursive unsolvability of Post's problem of “Tag” and other topics in the theory of Turing machines,Annals of Math. 74 (1961), 437–455.
W. F. Ogden, Intercalation theorems for stack languages, Symposium on Theory of Computing, Marina del Rey, California, pp. 31–42, 1969.
Author information
Authors and Affiliations
Additional information
Also formerly with System Development Corporation, Santa Monica, California. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-70-C-0023; by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR No. F44620-70-C-0013; and by NSF Grant No. GJ454.
Rights and permissions
About this article
Cite this article
Book, R., Ginsburg, S. Multi-stack-counter languages. Math. Systems Theory 6, 37–48 (1972). https://doi.org/10.1007/BF01706072
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01706072