\input zb-basic
\input zb-ioport
\iteman{io-port 01823194}
\itemau{Lindenstrauss, Noami; Dershowitz, Nachum}
\itemti{Abstract and-parallel machines.}
\itemso{Comput. Artif. Intell. 19, No.5, 475-493 (2000).}
\itemab
There is a presentation of several abstract models regarding parallel computation which are suited to symbolic programming languages. One starts with the and-parallel Turing machine viewed as a generalization of the deterministic one in which infinite tape is replaced by an infinite tree-like tape. On this tape, processors work in parallel. The parallel rewriting machine with Interrupt is a more powerful model and is described in chapters 3 and 4. These types of models are capable to simulate counting Turing machines, nondeterministic as well as alternating Turing machines in polynomial time. One of advantages of rewrite rules is that machine is very easy to program. By means of some examples it is shown that under the restriction of polylogarithmic time and a space of logarithmic depth, the above introduced models can be seen as models of realistic machines.
\itemrv{Claudia Simionescu-Badea (Wien)}
\itemcc{}
\itemut{parallel computation; rewriting; Turing machines}
\itemli{}
\end