×

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


MSC:

68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDF BibTeX XML Cite
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)
[12] Hack, M., Petri net languages, (), 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, 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. 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.