Preprint series: 99-29, Reports on Computer Science

The paper is published: in: Words, Sequences, Grammars, Languages: where Biology, Computer Science, Linguistics and Mathematics Meet, Vol I. (C. Martin-Vide and V. Mitrana Eds.), Kluwer, Dordrecht 2000, pp. 115 - 125.

MSC:

68Q05 Models of computation (abstract processors, Turing machines, etc.), See also {03D10}

03D55 Hierarchies

68Q45 Formal languages, See also {03D05, 20M35, 94A45}

Abstract: Using a specific model of communicating deterministic Turing machines
we prove that the class of \omega-languages accepted by deterministic
Turing machines via complete non-oscillating (complete oscillating)
runs on the input coincides with the class of \Pi_3-definable
(\Sigma_3-definable, respectively) \omega-languages.

Upload: 1999-12-06

Update: 2002 -09 -23