-
-
Autor*innen: Farwer, Berndt; Kudlek, Manfred; Rölke, Heiko
Titel: Concurrent turing machines
In: Fundamenta Informaticae, 79 (2007) 3/4, S. 303-317
Dokumenttyp: 3a. Beiträge in begutachteten Zeitschriften; Aufsatz (keine besondere Kategorie)
Sprache: Englisch
Schlagwörter: Informatik; Modell; Automation; Petri-Netz
Abstract (english): We define Concurrent Turing Machines (CTMs) as Turing machines with Petri nets as finite control. This leads to machines with arbitrary many tape heads, thus subsuming any class of (constant) k-head Turing machines. Space, time, and head complexity classes are introduced and discussed for some examples. These also show the differences of various acceptance conditions that are defined for CTMs. We specify a simulation algorithm showing that CTMs are not more powerful than sequential Turing machines with respect to the class of accepted languages regardless of the acceptance condition. A plug-in for the Renew tool allows the execution of CTMs. Similar extensions are envisaged for other machine models. (DIPF/Author)
DIPF-Abteilung: Informationszentrum Bildung