Concurrent turing machines

Berndt Farwer; Manfred Kudlek; Heiko Roelke

Concurrent turing machines

Berndt Farwer^*, Manfred Kudlek, Heiko Roelke

^*Awdur cyfatebol y gwaith hwn

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

Crynodeb

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 showing the difference of various acceptance conditions that are defined for CTMs. Nevertheless, we show that CTMs can be simulated by TMs.

Concurrent Turing machines correspond to a class of multiset rewriting systems. The definition of a CTMs as a rewrite theory avoids the need for encoding multisets as words and using an equivalence relation on configurations. Multiset rewriting lends itself to be used in rewriting systems and tools like the rewriting engine Maude. For the rewriting system, a configuration is given by a varying sequence of strings and multisets.

Iaith wreiddiol	Saesneg
Tudalennau (o-i)	303-317
Nifer y tudalennau	15
Cyfnodolyn	Fundamenta Informaticae
Cyfrol	79
Rhif cyhoeddi	3-4
Statws	Cyhoeddwyd - 2007
Digwyddiad	Workshop on the Concurrency Specification and Programming (CS&P) - Wandlitz, Gambia Hyd: 27 Medi 2006 → 29 Medi 2006

Mynediad at Ddogfen

https://content.iospress.com/articles/fundamenta-informaticae/fi79-3-4-05

Dyfynnu hyn

@article{814c60be55a243c08e38534c1a9969f2,

title = "Concurrent turing machines",

abstract = "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 showing the difference of various acceptance conditions that are defined for CTMs. Nevertheless, we show that CTMs can be simulated by TMs.Concurrent Turing machines correspond to a class of multiset rewriting systems. The definition of a CTMs as a rewrite theory avoids the need for encoding multisets as words and using an equivalence relation on configurations. Multiset rewriting lends itself to be used in rewriting systems and tools like the rewriting engine Maude. For the rewriting system, a configuration is given by a varying sequence of strings and multisets.",

author = "Berndt Farwer and Manfred Kudlek and Heiko Roelke",

year = "2007",

language = "English",

volume = "79",

pages = "303--317",

journal = "Fundamenta Informaticae",

issn = "0169-2968",

publisher = "IOS Press",

number = "3-4",

note = "Workshop on the Concurrency Specification and Programming (CS&P) ; Conference date: 27-09-2006 Through 29-09-2006",

}

TY - JOUR

T1 - Concurrent turing machines

AU - Farwer, Berndt

AU - Kudlek, Manfred

AU - Roelke, Heiko

PY - 2007

Y1 - 2007

N2 - 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 showing the difference of various acceptance conditions that are defined for CTMs. Nevertheless, we show that CTMs can be simulated by TMs.Concurrent Turing machines correspond to a class of multiset rewriting systems. The definition of a CTMs as a rewrite theory avoids the need for encoding multisets as words and using an equivalence relation on configurations. Multiset rewriting lends itself to be used in rewriting systems and tools like the rewriting engine Maude. For the rewriting system, a configuration is given by a varying sequence of strings and multisets.

AB - 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 showing the difference of various acceptance conditions that are defined for CTMs. Nevertheless, we show that CTMs can be simulated by TMs.Concurrent Turing machines correspond to a class of multiset rewriting systems. The definition of a CTMs as a rewrite theory avoids the need for encoding multisets as words and using an equivalence relation on configurations. Multiset rewriting lends itself to be used in rewriting systems and tools like the rewriting engine Maude. For the rewriting system, a configuration is given by a varying sequence of strings and multisets.

M3 - Article

SN - 0169-2968

VL - 79

SP - 303

EP - 317

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 3-4

T2 - Workshop on the Concurrency Specification and Programming (CS&P)

Y2 - 27 September 2006 through 29 September 2006

ER -

Concurrent turing machines

Crynodeb

Mynediad at Ddogfen

Ôl bys

Dyfynnu hyn