Variations on the technique of Ďuriš and Galil
type: Item
instance of: scholarly article
title: Variations on the technique of Ďuriš and Galil
zbMATH Open document ID: 0576.68061
DOI: 10.1016/0022-0000(85)90005-4
author: Marek Chrobak
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: 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).
reviewed by: Matthias Jantzen
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3922006
zbMATH Keywords: two-way counter automata
zbMATH Keywords: non-closure properties
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90005-4
OpenAlex ID: W2000884591
cites work: Q3219134
cites work: Fooling a two way automaton or one pushdown store is better than one counter for two way machines
cites work: Q3945613
cites work: Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
cites work: Two-Way Counter Machines and Diophantine Equations
cites work: Q5592246
cites work: Transformational methods and their application to complexity problems
description: scientific article; zbMATH DE number 3922006