Synchronized product of linear bounded machines

DOI10.1007/3-540-48321-7_30MaRDI QIDQ4934344zbMATH OpenFDO

Authors Étienne Payet, Teodor Knapik

Publication date 7 November 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48321-7_30

zbMATH Keywords

associated graphsfirst-order theoryobservational equivalencesingle-tape machinessynchronized producttransformations on multi-tape linear bounded machines

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Review text

Two types of transformations on multi-tape linear bounded machines with a single, read only input tape are studied. The first one is similar to the simulation of a multi-tape Turing machine by a single-tape one. The second one reflects communications of several single-tape machines. It is shown in the paper that the considered transformations preserve observational equivalence of associated graphs and are closed under synchronized product. It is also estabished that the first-order theory of the graphs of linear bounded machines is not decidable. For the entire collection see [Zbl 0921.00033].

Recommendations

• Mathematical Foundations of Computer Science 2005
• Linearly bounded infinite graphs
• Synchronized tree automata
• On the open problem of Ginsburg concerning semilinear sets and related problems
• scientific article; zbMATH DE number 6665216

Cited in

(1)

• Linearly bounded infinite graphs

This page was built for publication: Synchronized product of linear bounded machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4934344)