Observation of String-Rewriting Systems
Observation of String-Rewriting Systems
复制标题
字符串重写系统的观察
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Peter Leupold
中科院分区：
文献类型：
--
作者：
M. Cavaliere;Peter Leupold
理论计算机科学中的计算模型通常由执行某种类型过程的设备组成，如图灵机及其计算或语法及其派生。在过程停止后，只有一些最终输出被视为结果。在向这样的设备添加观察者时，可以获得整个过程的协议，然后将其用作计算的结果。在最近的几篇文章中，这种方法被证明经常大大超过所观察到的系统的能力。
在这里，我们将这种架构应用到字符串重写系统。它们接收一个字符串作为输入，然后观察者和决策者的组合确定这个字符串是否被接受。该决定仅基于所执行的重写过程。首先，我们确定的权力画家，上下文无关，和逆上下文无关的重写系统的McNaughton语言。然后，这些被调查的重写/观察员系统的组成部分，我们得到的上下文敏感和递归可重写语言类的特征。最后，我们调查了一些限制，即表征一些系统，观察不增加功率。
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.