Space-bounded OTMs and REG∞

Article type: Research Article

Authors: Carl, Merlin^{; *}

Affiliations: Institut für mathematische, technische und naturwissenschaftliche Bildung, Abteilung für Mathematik und ihre Didaktik, Europa-Universität Flensburg, Abbreviate US states, Germany. merlin.carl@uni-flensburg.de

Correspondence: [*] Corresponding author. merlin.carl@uni-flensburg.de.

Abstract: An important theorem in classical complexity theory is that REG=LOGLOGSPACE, 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) and 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, which is a transfinite analogue of LOGLOGSPACE⊆REG; the other direction, however, is easily seen to fail.

Keywords: Regular language, deterministic finite automaton, complexity theory, ordinal turing machine, ordinal computability

DOI: 10.3233/COM-200327

Journal: Computability, vol. 11, no. 1, pp. 41-56, 2022