×

zbMATH — the first resource for mathematics

Simulation problems for one-counter machines. (English) Zbl 0963.68094
Pavelka, Jan (ed.) et al., SOFSEM ’99: Theory and practice of informatics. 26th conference on Current trends in theory and practice of informatics. Milovy, Czech Republic, November 27-December 4, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1725, 404-413 (1999).
Summary: We consider decidability questions for simulation preorder (and equivalence) for processes generated by one-counter machines. We sketch a proof of decidability in the case when testing for zero is not possible, and demonstrate the undecidability in the general case.
For the entire collection see [Zbl 0931.00042].

MSC:
68Q45 Formal languages and automata
Keywords:
decidability
PDF BibTeX XML Cite