ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY
Volume 1, Number 1, 1998, 73 - 83

 

String Functions Based Machines
Gheorghe PAUN
Institute of Mathematics of the Romanian Academy
PO Box 1 - 764, 70700 Bucuresti, Romania
E-mail: gpaun@imar.ro

 

Abstract.
We propose and briefly investigate a general framework for studying abstract machines (automata) processing strings. One starts from a basic set of partial functions on strings over a given alphabet, and one considers machines which use these string functions according to a specified control mechanism; we deal here with graph control, regular control language, and prescribed finite sequences of functions as control mechanisms.
Their relationships are examined and, for a particular set of string functions, inspired from [4], one proves that most variants of the above mentioned types of machines are as powerful as Turing machines. A series of topics for further research are also formulated.