Synchronized product of linear bounded machines (Q4934344)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1390078
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Synchronized product of linear bounded machines |
scientific article; zbMATH DE number 1390078 |
Statements
7 November 2000
0 references
transformations on multi-tape linear bounded machines
0 references
single-tape machines
0 references
observational equivalence
0 references
associated graphs
0 references
synchronized product
0 references
first-order theory
0 references
0.7577873468399048
0 references
0.7545042634010315
0 references
0.7270780205726624
0 references
0.7248396277427673
0 references
Synchronized product of linear bounded machines (English)
0 references
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].
0 references
