Abstract
The paper investigates the behavior of multi-tape automata, i.e. accepting devices the input of which consists of a certain number n of tapes with a one-way read-only head on each of them. In each step depending on the current state some of these heads are activated and read one symbol from the corresponding tape. Depending on the symbols read and on the numbers of the tapes from which they are read the current state is changed in a deterministic respectively nondeterministic way. The behavior of the automaton is the set of all n-tuples of words which can be read completely by the automaton if it is started in an initial state, and which can transit it to a designated final state. Thereby we make no use of endmarkers. In the first two sections we characterize the behavior of infinite and finite, deterministic and nondeterministic multi-tape automata, in the last section we apply the results to a so far unsolved problem from the theory of nondeterministic generalized sequential machines.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Bibliographical remarks
Notation and terminology are used as in
Starke, P. H.: Abstract Automata. North-Holland Publ. Co., Amsterdam 1972.
Papers on multi-tape automata
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. & Dev. 3 (1959) 114–125
Rosenberg, A.L.: On n-tape finite state acceptors. IEEE Conf. Rec. Switch. Circ. Th. & Log. Design (5th Ann. Symp.) New York 1964.
Fischer, P.C., Rosenberg, A.L.: Multi-tape one-way nonwriting automata. J. Computer & Systems Sci. 2 (1968).
Makarevski, A., Stockaja, E: Predstavimost v determinirovannyh mnogolentočnyh avtomatah. Kibernetika (Kiev) 4 1969
Stockaja, E.: O mnogolentočnyh avtomatov bes konečnyh markerov. Avtomatika i Telemehanika 9 (1971) 105–110.
Papers on nondeterministic generalized sequential machines
Elgot, C.C., Mezei, J.E.: On relations defined by generalized finite automata. IBM J.Res.& Dev. 9 (1965) 47–68.
Griffiths, T.V.: The unsolvability of the equivalence problem for e-free nondeterministic generalized machines. J. ACM 15 (1968) 3, 409–413.
Grabowski, J.: Anwendung topologischer Methoden in der Theorie der ND-Automaten. Elektron. Inf.-verarb. u. Kybernetik 9 (1973) 10, 615–633.
The proofs of the theorems in the present paper are found in
Starke, P.H.: Über die Darstellbarkeit von Relationen in Mehrbandautomaten. To appear in: Elektron. Inf.-verarb. u. Kybernetik.
Starke, P.H.: Entscheidungsprobleme für autonome Mehrbandautomaten. To appear in: Z. f. Math. Logik u. Grundl. d. Math.
Starke, P.H.: Über eine Anwendung der Theorie der Mehrbandautomaten in der Theorie der asynchronen ND-Automaten. In preparation.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1975 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Starke, P.H. (1975). On the representability of relations by deterministic and nondeterministic multi-tape automata. In: Bečvář, J. (eds) Mathematical Foundations of Computer Science 1975 4th Symposium, Mariánské Lázně, September 1–5, 1975. MFCS 1975. Lecture Notes in Computer Science, vol 32. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-07389-2_186
Download citation
DOI: https://doi.org/10.1007/3-540-07389-2_186
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-07389-5
Online ISBN: 978-3-540-37585-2
eBook Packages: Springer Book Archive