Observation of String-Rewriting Systems

Issue title: SPECIAL ISSUE MCU2004

Article type: Research Article

Authors: Cavaliere, Matteo | Leupold,

Affiliations: Department of Computer Science and Artificial Intelligence University of Sevilla, Spain. E-mail: [email protected] | Research Group on Mathematical Linguistics Rovira i Virgili University, Tarragona, Spain. E-mail: [email protected]

Abstract: Models of computation in theoretical computer science very frequently consist of a device performing some type of process, like a Turing machine and its computation or a grammar and its derivation. After the process halts, only some final output is regarded as the result. In adding an observer to such a device, one can obtain a protocol of the entire process and then use this as the result of the computation. In several recent articles this approach has proved to often exceed greatly the power of the observed system. Here we apply this architecture to string-rewriting systems. They receive a string as input, and a combination of observer and decider then determines whether this string is accepted. This decision is based only on the rewriting process performed. First we determine the power of painter, context-free, and inverse context-free rewriting systems in terms of McNaughton languages. Then these are investigated as components of rewriting/observer systems, and we obtain characterizations of the classes of context-sensitive and recursively enumerable languages. Finally we investigate some limitations, i.e. characterize some systems, where observation does not increase power.

Keywords: String-Rewriting, McNaughton Languages, Observation

Journal: Fundamenta Informaticae, vol. 74, no. 4, pp. 447-462, 2006