On the intersection of the class of linear context-free languages and the class of single-reset languages
| Autor: | K W Wagner |
|---|---|
| Rok vydání: | 1986 |
| Předmět: |
Discrete mathematics
Theoretical computer science Computer science Comparison of multi-paradigm programming languages Context-free language Abstract family of languages Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Second-generation programming language Cone (formal languages) Computer Science Applications Theoretical Computer Science Class-based programming TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Signal Processing Formal language Computer Science::Programming Languages Computer Science::Formal Languages and Automata Theory Information Systems Counterexample |
| Zdroj: | Information Processing Letters. 23:143-146 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/0020-0190(86)90114-6 |
| Popis: | In [2,8] it has been conjectured that the intersection of the class of linear context-free languages (i.e., languages accepted by nondeterministic machines with a one-way input tape and a one-reversal pushdown) and the class of single-reset languages (i.e., languages accepted by nondeterministic machines with a one-way input tape and a single-reset tape) coincides with the class of one-reversal one-counter languages (i.e., languages accepted by nondeterministic machines with a one-way input tape and a one-reversal counter). In the present paper we disprove this conjecture by constructing a counterexample. In other words, we show that (within this context) counters are not the intersection of pushdowns and queues. In [1], the related conjecture has been stated that the intersection of the class of linear contextfree languages and the class of one-counter languages (i.e., languages accepted by nondeterministic machines with a one-way input tape and a counter) coincides with the class of one-reversal one-counter languages. Starrting from the abovementioned result (which was included in an earlier version of the present paper), this conjecture has been disproved by Brandenburg [4]. Stimulated by the result in [4], we have investigated the question of whether at least the intersection of all three classes, namely the class of linear context-free languages, the class of single-reset languages, and the class of one-counter languages, coincides with the class of one-reversal one-counter languages. We show that even this is not true by constructing a counterexample which is simultaneously a counterexample to the conjecture in [2,8] as well as the conjecture in [1]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|