Concurrent turing machines

Berndt Farwer*, Manfred Kudlek, Heiko Roelke

*Awdur cyfatebol y gwaith hwn

    Allbwn ymchwil: Cyfraniad at gyfnodolynErthygladolygiad gan gymheiriaid


    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 wreiddiolSaesneg
    Tudalennau (o-i)303-317
    Nifer y tudalennau15
    CyfnodolynFundamenta Informaticae
    Rhif cyhoeddi3-4
    StatwsCyhoeddwyd - 2007
    DigwyddiadWorkshop on the Concurrency Specification and Programming (CS&P) - Wandlitz, Gambia
    Hyd: 27 Medi 200629 Medi 2006

    Ôl bys

    Gweld gwybodaeth am bynciau ymchwil 'Concurrent turing machines'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

    Dyfynnu hyn