Acceptance of ω-Languages by Communicating Deterministic Turing Machines

Rudolf Freund () and Ludwig Staiger ()
Additional contact information
Rudolf Freund: Technical University of Wien, Institute of Computer Languages
Ludwig Staiger: Martin-Luther- University at Halle- Wittenberg, Institute of Informatics

Chapter Chapter 10 in Where Mathematics, Computer Science, Linguistics and Biology Meet, 2001, pp 115-125 from Springer

Abstract: Abstract 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.

Keywords: Turing Machine; Finite Automaton; Input Tape; Input Component; Transition Machine (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-94-015-9634-3_10

Ordering information: This item can be ordered from
http://www.springer.com/9789401596343

DOI: 10.1007/978-94-015-9634-3_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().