2001 | OriginalPaper | Buchkapitel
Acceptance of ω-Languages by Communicating Deterministic Turing Machines
verfasst von : Rudolf Freund, Ludwig Staiger
Erschienen in: Where Mathematics, Computer Science, Linguistics and Biology Meet
Verlag: Springer Netherlands
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Using a specific model of communicating deterministic Turing machines we prove that the class of ω-languages accepted by deterministic Turing machines via complete non-oscillating (complete oscillating) runs on the input coincides with the class of ∏3-definable (Σ3-definable, respectively) ω-languages.