Multiprocessor automata
type: Item
instance of: scholarly article
title: Multiprocessor automata
zbMATH Open document ID: 0653.68044
DOI: 10.1016/0020-0190(87)90172-4
author: Anatoli O. Buda
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: The notion of multiprocessor automata is introduced. The multiprocessor automaton may be thought of as the simplest model of parallel computations: there are more than one processors reading information from the tape simultaneously, and the switching function for each processor depends on the inner states of all processors on the step of computations. We prove some results on the hierarchies of two-way and one-way multiprocessor automata languages.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 4066338
zbMATH Keywords: multihead automaton
zbMATH Keywords: formal languages hierarchy
zbMATH Keywords: multiprocessor automata
zbMATH Keywords: model of parallel computations
zbMATH Keywords: switching function
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90172-4
OpenAlex ID: W2912200930
cites work: Q3687746
cites work: On non-determinacy in simple computing devices
cites work: One-way simple multihead finite automata
description: scientific article; zbMATH DE number 4066338