Space-Bounded OTMs and REG^{\infty}
From MaRDI portal
Publication:6289110
DOI10.3233/COM-200327arXiv1707.05297MaRDI QIDQ6289110FDOQ6289110
Authors: Merlin Carl 
Publication date: 17 July 2017
Abstract: 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.
Automata and formal grammars in connection with logical questions (03D05) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Turing machines and related notions (03D10)
This page was built for publication: Space-Bounded OTMs and REG$^{\infty}$
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6289110)
