Variations on the technique of Ďuriš and Galil (Q1064791): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3219134 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fooling a two way automaton or one pushdown store is better than one counter for two way machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3945613 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two-Way Counter Machines and Diophantine Equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5592246 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transformational methods and their application to complexity problems / rank | |||
Normal rank |
Latest revision as of 19:15, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Variations on the technique of Ďuriš and Galil |
scientific article |
Statements
Variations on the technique of Ďuriš and Galil (English)
0 references
1985
0 references
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).
0 references
two-way counter automata
0 references
non-closure properties
0 references
0 references
0 references