Variations on the technique of Ďuriš and Galil (Q1064791): Difference between revisions

The crossing sequence technique used by Ďuriš and Galil in showing that the family 2DC (of languages accepted by deterministic two- way counter automata) is strictly included in the family 2DPDA (of languages accepted by deterministic two-way pushdown automata) is modified and then used to show that deterministic two-way counter automata are less powerful than their nondeterministic version. Also the class 2DC is shown to be incomparable with the class DCFL and some non- closure properties of 2DC are proved, too. This paper is an improved presentation of the author's work in Lect. Notes Comput. Sci. 176, 240- 244 (1984; Zbl 0555.68047).