|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 7 van 18 gevonden artikelen
| Titel: |
Limited Automata and Context-Free Languages |
| Auteur: |
Pighizzini, Giovanni Pisoni, Andrea |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 136 (2015) nr. 1-2 pagina's 157-176 |
| Jaar: |
2015-02-06 |
| Inhoud: |
Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 7 van 18 gevonden artikelen
| << vorige | volgende >> |