Space-Bounded OTMs and REG$^{\infty}$
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2017
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914576399859712 |
|---|---|
| author | Carl, Merlin |
| author_facet | Carl, Merlin |
| contents | An important theorem in classical complexity theory is that LOGLOGSPACE=REG, i.e. that languages decidable with double-logarithmic space bound are regular. We consider a transfinite analogue of this theorem. To this end, we introduce deterministic ordinal automata (DOAs), show that they satisfy many of the basic statements of the theory of deterministic finite automata and regular languages. We then consider languages decidable by an ordinal Turing machine (OTM), introduced by P. Koepke in 2005 and show that if the working space of an OTM is of strictly smaller cardinality than the input length for all sufficiently long inputs, the language so decided is also decidable by a DOA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1707_05297 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | Space-Bounded OTMs and REG$^{\infty}$ Carl, Merlin Logic An important theorem in classical complexity theory is that LOGLOGSPACE=REG, i.e. that languages decidable with double-logarithmic space bound are regular. We consider a transfinite analogue of this theorem. To this end, we introduce deterministic ordinal automata (DOAs), show that they satisfy many of the basic statements of the theory of deterministic finite automata and regular languages. We then consider languages decidable by an ordinal Turing machine (OTM), introduced by P. Koepke in 2005 and show that if the working space of an OTM is of strictly smaller cardinality than the input length for all sufficiently long inputs, the language so decided is also decidable by a DOA. |
| title | Space-Bounded OTMs and REG$^{\infty}$ |
| topic | Logic |
| url | https://arxiv.org/abs/1707.05297 |