×
Greibach, S. A.

Remarks on blind and partially blind one-way multicounter machines. (English) Zbl 0389.68030

Theor. Comput. Sci. 7, 311-324 (1978).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0389.68030

Cited in 4 Reviews
Cited in 113 Documents

MSC:

68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Cite Review PDF
Full Text: DOI

References:

[1] Baker, B. S.; Book, R. V., Reversal-bounded multipushdown machines, J. Comput. System Sci., 3, 315-332 (1974) · Zbl 0309.68043
[2] Boasson, L., Two iteration theorems for some families of languages, J. Comput. System Sci., 7, 583-596 (1973) · Zbl 0298.68053
[3] Book, R.; Greibach, S., Quasirealtime languages, Math. Syst. Theory, 4, 97-111 (1970) · Zbl 0188.33102
[4] Book, R. V.; Greibach, S.; Ibarra, O.; Wegbreit, B., Tape-bounded Turing acceptors and principal AFLs, J. Comput. System Sci., 4, 622-625 (1970) · Zbl 0206.28703
[5] Book, R. V.; Wegbreit, B., A note on AFLs and bounded erasing, Information and Control, 19, 18-29 (1971) · Zbl 0237.68021
[6] Fischer, P. C.; Meyer, A. R.; Rosenberg, A. L., Counter machines and counter languages, Math. Syst. Theory, 2, 265-283 (1968) · Zbl 0165.32002
[7] Ginsburg, S.; Greibach, S., Abstract families of languages, Memoirs Amer. Math. Soc., 87, 1-32 (1969) · Zbl 0194.31402
[8] Ginsburg, S.; Greibach, S., Principal AFL, J. Comput. System. Sci., 4, 308-338 (1970) · Zbl 0198.03102
[9] Ginsburg, S.; Greibach, S., On AFL Generators for finitely encoded AFA, J. Comput. System. Sci., 7, 1-27 (1973) · Zbl 0249.68025
[10] Greibach, S. A., Remarks on the complexity of nondeterministic counter languages, Theoret. Comput. Sci., 1, 269-288 (1976) · Zbl 0332.68039
[11] Greibach, S.; Ginsburg, S., Multi-tape AFA, J. ACM, 19, 192-221 (1972) · Zbl 0241.68031
[12] Hack, M., Petri net languages, (Computation Structures Group Memo 124 (1975), Massachusetts Institute of Technology), Project MAC
[13] Hartmanis, J.; Hopcroft, J., What makes some language theory problems undecidable, J. Comput. System Sci., 3, 196-217 (1969) · Zbl 0198.03001
[14] Minsky, M., Recursive unsolvability of Post’s problem of Tag and other topics in the theory of Turing machines, Annals Math., 74, 437-455 (1961) · Zbl 0105.00802
[15] Paterson, J. L., Computation sequence sets, J. Comput. System Sci., 13, 1-24 (1976) · Zbl 0354.68100
[16] Sacerdote, G. S.; Tenney, R. L., The decidability of the reachability problem for vector addition systems, Boulder, Colorado. Boulder, Colorado, Proc. Ninth Ann. ACM Symp. on Theory of Computing, 61-76 (May 1977)
[17] Wrathall, C., Characterizations of the Dyck sets, RAIRO, 11 (1977) · Zbl 0354.68104
[18] Latteux, M., Cônes rationneis commutativement Clos, RAIRO Informat. Théorique, 11, 29-51 (1977) · Zbl 0354.68103
[19] Arnold, A.; Latteux, M., Vector addition systems and semi-Dyck languages (1977), unpublished manuscript
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.